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 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.
Dry Run: [5, 1, 4, null, null, 3, 6]
Root: 5
| Node | Current Range | Check | Action |
|---|---|---|---|
| 5 | (-Inf, +Inf) |
Valid | Check Left, Check Right |
| 1 (Left) | (-Inf, 5) |
1 < 5? Yes | Valid. |
| 4 (Right) | (5, +Inf) |
4 > 5? NO | Invalid! Return False |
Edge Cases & Common Mistakes
- Equal Values: BST definition usually implies strict inequality. Check problem constraints. Usually
left < node < right. - Integer Overflow: Use
Longornullfor infinity bounds if node values can beINT_MAX. The code below uses no bound at all (None/null) instead of an infinity, so it works for every integer value.
Solution
Range Validation approach.
Validate Binary Search Tree Code
1var isValidBST = function(root) {2 function valid(node, low, high) {3 if (!node) return true;4 if ((low !== null && node.val <= low) || (high !== null && node.val >= high)) {5 return false;6 }7 return valid(node.left, low, node.val) && valid(node.right, node.val, high);8 }910 return valid(root, null, null);11};