Return true if the tree is a valid binary search tree: for every node, all values
in its left subtree are strictly smaller and all values in its right subtree are
strictly larger.
isBinarySearchTree(root)
Input format: level-order with x for missing children. An empty tree is a valid
BST.
5 3 8 2 4 7 9 // → true
5 3 8 2 6 // → false (6 is in 5's left subtree)
(empty) // → true
The tempting first attempt: check locally, each node's immediate left child is smaller, right child is larger. That's not enough. A node deep in a left subtree could be smaller than its immediate parent (passing the local check) but larger than some ancestor several levels up. The BST property is about a node versus every ancestor whose subtree it belongs to, not just its direct parent.
Each node needs to know the full range it's allowed to hold, based on every ancestor decision made to reach it — an open interval, tightened as you descend:
At each node, check its value strictly falls within the range handed down. If not, invalid — stop. If it does, recurse left with the upper bound tightened to this node's value, and right with the lower bound tightened. A missing node trivially satisfies any range. The tree is valid exactly when every node passes its check.
Threading accumulated constraints from every ancestor means each node is checked against the full set of rules it must obey, not just its immediate parent's rule — catching violations against grandparents or higher ancestors. Each node does constant work, visited once — O(n) time, O(h) space for the recursion stack.
def is_binary_search_tree(root):
def valid(node, low, high):
if node is None:
return True
if node.val <= low or node.val >= high:
return False
return valid(node.left, low, node.val) and valid(node.right, node.val, high)
return valid(root, float("-inf"), float("inf"))
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.