Trying to determine if a tree is a valid binary search tree

Question

The code below passes all test cases where we try to determine if a tree is a valid BST.

public static boolean validateBst(BST tree) {
    return isValid(tree, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

public static boolean isValid(BST tree, int min, int max) {
    if (tree == null) {
        return true;
    }

    if (tree.value < min || tree.value >= max) {
        return false;
    }

    return isValid(tree.left, min, tree.value) && isValid(tree.right, tree.value, max);
}

The code above checks if a tree is a valid BST. The logic is simple, if a tree is null then it is a BST. If the value of the tree is less than the min and greater than the max we return false as it is not a valid BST condition.

The issue I have is when i change the following line:

if (tree.value < min || tree.value >= max) {
    return false;
}

To the following

if (tree.value > min && tree.value < max) {
    return true
}

The code does not pass all the test cases. This is confusing to me because I feel like both statements are saying the same thing.

The first if statement is saying if the value of the tree/node is less than the min or more than the max then you are not a valid BST and the second statement is saying if your value is within the range of min and max you are a valid bst.

So please help me understand why when i change that line my code does not pass all the test cases.

Is it because the moment i change that line and return true, i would not be checking the rest of the tree?

Answer 1

The code does not pass all the test cases. This is confusing to me because I feel like both statements are saying the same thing.

There are two problems here, the first one can be fixed easily, the latter requires a more extensive code rewrite.

First of all, the negation of x<y is x≥y. Indeed, with x<y we exclude the possibility that x = y, but if we negate the condition, we should allow this case.

Next you can not just return true if the node has a value between min and max. A tree. Indeed: if the node is between the bounds that is good news, but the children of the node can still not be valid binary search trees, and thus we need to recurse on the children.

We can thus write this as:

if(min <= tree.value && tree.value < max){
       return isValid(tree.left,min,tree.value) && isValid(tree.right,tree.value,max);
}
return false;

Note that, depending on how you exactly implemented the search tree, you need to alter tree.value < max to tree.value <= max as well. Since in some trees (like balanced ones), both the left and the right subchild sometimes contain equivalent values. This however might not be very important if your search tree only contains distinct values, which usually is the case.