Test cases missing

• There should be a test case where some nodes have values equal to Integer.MIN_VALUE and Integer.MAX_VALUE;

This solution is accepted and shouldn't be:

``````public boolean isValidBST(TreeNode root) {
if (root == null) return true;
return isValidBST(root.left,Integer.MIN_VALUE, root.val)
&& isValidBST(root.right,root.val,Integer.MAX_VALUE);
}

public boolean isValidBST(TreeNode root, int smallest, int largest) {
if (root == null) return true;
if (root.val > smallest && root.val < largest)
return isValidBST(root.left,smallest, root.val)
&& isValidBST(root.right,root.val,largest);
else
return false;
}``````

• Yes, you are right. Adding test case which contains INT_MIN or INT_MAX means your code no longer works.

I decided not to include these edge cases, as a good programmer should be able to pinpoint these edge cases and fix their code anyway. As a good followup question, can you modify your code to handle these edge cases?

Update: I've strengthen the test cases to prevent code that relies on INT_MIN or INT_MAX from passing. Thanks for the feedback.

• is this right? or anyone has a better solution for min_value and max_value (except for Long.MAX_VALUE)

``````public boolean isValidBST(TreeNode root) {
//initial that: meet MIN_VALUE = false and MAX_VALUE = false
return validRSTRecursive(root,Integer.MIN_VALUE,Integer.MAX_VALUE,false,false);
}
public boolean validRSTRecursive(TreeNode node,int lower, int upper, boolean MinValueMeet, boolean MaxValueMeet) {
if(node == null) {
return true;
}

if(node.val == Integer.MIN_VALUE) {      //care about test case: node.val = MIN_VALUE
if(MinValueMeet) {                   //can only meet MIN_VALUE once
return false;
}
MinValueMeet = true;
//left node should be null and recursively to right tree
return (node.left == null) && validRSTRecursive(node.right,node.val,upper,MinValueMeet,MaxValueMeet);
}
if(node.val == Integer.MAX_VALUE) {    //care about test case: node.val = MAX_VALUE
if(MaxValueMeet) {                 //can only meet MAX_VALUE once
return false;
}
MaxValueMeet = true;
//right node should be null and recursively to left tree
return (node.right == null) && validRSTRecursive(node.left,lower,node.val,MinValueMeet,MaxValueMeet);
}

//no meet MIN_VALUE or MAX_VALUE
if(node.val > lower && node.val < upper ) {
return validRSTRecursive(node.left,lower,node.val,MinValueMeet, true) && validRSTRecursive(node.right,node.val,upper, true,MaxValueMeet);
} else {
return false;
}
}``````

• This post is deleted!

• //Recursive solution without using INT_MAX and INT_MIN

//For the binary tree, only one left side path and one right side path use single bound.

//All other branches use double bounds.

``````class Solution {
public:
enum class flag {LOW, UPPER};

//flag f indicates the value is lower or upper bound
bool single_bound(TreeNode *node, flag f, int bound) {
if (node == NULL) return true;

if (f == flag::LOW) {
if (node->val <= bound) return false;
return double_bound(node->left, bound, node->val) && single_bound(node->right, flag::LOW, node->val);
} else if (f == flag::UPPER) {
if (node->val >= bound) return false;
return single_bound(node->left, flag::UPPER, node->val) && double_bound(node->right, node->val, bound);
}
}

bool double_bound(TreeNode *node, int low, int upper) {
if (node == NULL) return true;
if (node->val >= upper || node->val <= low) return false;

return double_bound(node->left, low, node->val) && double_bound(node->right, node->val, upper);
}

bool isValidBST(TreeNode *root) {
if (root == NULL || root->left == NULL && root->right == NULL) return true;

return single_bound(root->left, flag::UPPER, root->val) && single_bound(root->right, flag::LOW, root->val);
}
};``````

• Your solution seems not right.
for example { 3, 2, #, 1, Integer.MIN_VALUE}
your algorithm will return true, however, MIN_VALUE is out side of the range (2, 3), the result should be false.

• thx, your example points out my bug. I have fixed the bug as you can see in the code.

return validRSTRecursive(node.left,lower,node.val,MinValueMeet, true) && validRSTRecursive(node.right,node.val,upper, true,MaxValueMeet);