Validate Binary Search Tree

Question

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true
Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

My code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:



        def helper(node, lower = float('-inf'), upper = float('inf')):
            if(not node):
                return True

            if(node.val<=lower or node.val>=upper):
                return False
            if not helper(node.right, node.val, upper):
                return False
            if not helper(node.left, lower, node.val):
                return False
            return True


        return helper(root)

The above code works well for all test cases. However, the code below does not.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:



        def helper(node, lower = float('-inf'), upper = float('inf')):
            if(not node):
                return True

            if(node.val<=lower or node.val>=upper):
                return False
            helper(node.right, node.val, upper)
            helper(node.left, lower, node.val)
            return True


        return helper(root)

What is the need for the extra IF conditions? Even without them, the functions should return false from the if condition below right? What am I missing here?

 if(node.val<=lower or node.val>=upper):
                    return False

Maybe renaming helper to is_subtree_within_bounds may help understand what's going on — rdas
When helper calls itself, then returns False as you say, it doesn’t exit the helper that called. That’s how function calls work and this is recursion at work. — quamrana

paxdiablo paxdiablo · Accepted Answer · 2020-03-11T22:33:31

You're basically asking what the difference is between:

if not helper(node.right, node.val, upper):
    return False
if not helper(node.left, lower, node.val):
    return False
return True

and:

helper(node.right, node.val, upper)
helper(node.left, lower, node.val)
return True

The first checks the return value from the helper calls and acts appropriately, returning false if the sub-tree is not a BST. The second checks the sub-trees then returns true no matter what.

This is important. The definition of a valid BST is that root is greater than root.left and less than root.right, and that both root.left and root.right are also valid BSTs.

By ignoring those return values, the only thing you're checking is that the top three nodes for a valid BST. In other words, this would pass despite being nowhere near valid:

    __4__
   /     \
  2       8
 / \     / \
3   1   9   7

Without returning the result at every level of recursion, you basically lose it.

Consider the code below, which is akin to the question you raised in a comment ("But inside the helper function, there is an if condition which return false right? How does that not come into play here?"):

def level2():
    return 42          # Returns '42'.

def level1():
    level2()           # Returns 'None', not '42'.

print(level1())        # Prints 'None'.

This prints None since, even though you return 42 at level two, that's thrown away at level one.

The correct method would change the level2() call into return level2().

As an aside, I'm not sure what value you're getting from upper and lower here.

The recursive definition of validity means that the only thing you need to check is the three immediate nodes and the sub-trees.

In other words, this would suffice (pseudo-code, even though it looks like Python, the latter being an ideal baseline for the former):

def isValidBst(node):
    # Empty tree is valid (or sub-tree, for that matter
    # but, since we never descend into a null, that's a
    # moot point).

    if node is null: return true

    # Check left value and sub-tree.

    if node.left is not null:
        if node.left.value >= node.value: return false
        if not isValidBst(node.left): return false

    # Check left value and sub-tree.

    if node.right is not null:
        if node.right.value <= node.value: return false
        if not isValidBst(node.right): return false

    # If there were no failures, including the possibility
    # we're at a leaf node, everything below this node is
    # okay.

    return true

Validate Binary Search Tree

1 Answers