FAANGPrep Sprint
Validate Binary Search Tree
Determine if a binary tree is a valid Binary Search Tree (BST).
Examples
Left (1) < 2 < Right (3).
5 is the root, yet its right child holds 4, a smaller key on the right side, so this is not a BST.
Problem Understanding
Check whether the binary tree under root is a valid Binary Search Tree (BST).
That holds when, at every node:
- Every key anywhere in its left subtree is less than its own key.
- Every key anywhere in its right subtree is greater than its own key.
- Both rules hold again inside each subtree.
Algorithm Strategy
Common Mistake: Just checking left.val < node.val and right.val > node.val is wrong. It fails for deeper levels (e.g., a node in the right subtree can be smaller than the root even though every parent-child pair looks correct).
Correct Approach: Range Validation (Top-Down DFS)
- Pass a valid range
(min, max)down to each node. - Root range:
(-Infinity, +Infinity). - When going Left, update max:
(min, node.val). - When going Right, update min:
(node.val, max). - If a node's value is not within
(min, max), returnfalse.
Interactive Visualization
EACH NODE MUST FIT (LOW, HIGH)
CALL valid(root)
Range
—
Valid BST
—
call stack
No calls in progress
Call valid(root) with no lower and no upper bound
Next
valid(5): it must lie strictly inside (−∞, +∞)
Tree
Each node is checked against the open range it was handed, shown under it. Going left caps the range at the parent’s value; going right raises its floor. The first node outside its range turns red.