How do you validate that a binary tree is a valid binary search tree?
You check two things at every node. The value has to be bigger than every value in the left sub-tree and smaller than every value in the right sub-tree.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def is_valid_bst(root):
return check(root, None, None)
def check(node, low, high):
if node is None:
return True
if low is not None and node.value <= low:
return False
if high is not None and node.value >= high:
return False
return check(node.left, low, node.value) and check(node.right, node.value, high)
So how does it work? The helper function takes three things. The node to check, the biggest value that the node is allowed to be, and the smallest value that it is allowed to be. Those two limits are the bounds that come from the ancestors.
At the root there are no bounds, so they are both nothing. When you go down into the left sub-tree, the value of the node becomes the upper bound. And when you go down into the right sub-tree, the value of the node becomes the lower bound.
the root bounds are (nothing, nothing)
the left child bounds are (nothing, the root value)
the right child bounds are (the root value, nothing)
And the reason you use two bounds and not just the parent is the subject of the next question in this topic.
And the complexity is O of n for the time, because every node is visited once, and O of h for the space because of the call stack.
So the rule to remember is this. Carry the bounds down the tree, and the value of every node has to sit inside them.
The last question in this topic shows why the simple check does not work.