Checking that [1, null, 1] and [1, 1] are valid Binary Search Trees

Question

What would be the possible Binary Search Tree of [1, null, 1] and [1, 1]? Will there be any difference at all?

My code verifies [1, 1] as BST but not [1, null, 1], and I don't understand why...

bool isBST(TreeNode* root, int max, int min){
    if(!root)
        return true;
    if((max!= NULL && max<=root->val) || (min!= NULL && min>root->val))
        return false;
    if(!isBST(root->left, root->val, min) || !isBST(root->right, max, root->val))
        return false;
    return true;
}
bool isValidBST(TreeNode* root) {
    int min =NULL, max = NULL;
    return isBST(root, NULL, NULL);
}

Why does my code not return true for [1, null, 1]?

Answer 1

The array format is usually a breadth-first order of the values in a tree, where null is a place holder for where there is no node.

So for instance [1, 1] is a representation of this tree:

      1
     /
    1

And [1, null, 1] is a representation of this tree:

       1
      / \
   null  1 

Which is:

       1 
        \
         1

Another, larger example: [10, 5, 8, 2, null, 6, null, 1, 3, null, 7] represents:

           10
          /  \
         5    8
        /    /
       2    6
      / \    \
     1   3    7

So, yes, there is a difference between [1, 1] and [1, null, 1].

The reason why your code does not consider the second one valid, is because of the comparison made in this line:

if((max!= NULL && max<=root->val) || (min!= NULL && min>root->val))
//                   ^^

You should allow a value to be equal to max, so correct as follows:

if((max!= NULL && max< root->val) || (min!= NULL && min>root->val))

Some other remarks:

• I find it confusing that your function first takes the max argument and then the min. Consider changing the order of these two parameters.

• Using NULL as initial value for min and max may lead to problems when your tree happens to have a value that is equal to NULL (in most environments 0 would be equal NULL). Consider using INT_MIN and INT_MAX respectively as initial values, and then you can also remove the extra conditions in your isBST function.