Validate Binary Search Tree: The Recursive Bounds Pattern
The recursive bounds solution to Validate Binary Search Tree, explained step by step with a worked walkthrough, JavaScript code, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Validate Binary Search Tree looks like a two-line check and traps almost everyone who treats it like one. The naive instinct — "each node is bigger than its left child and smaller than its right child" — passes plenty of trees that are not BSTs at all. The value that breaks the tree is often nowhere near the node it contradicts.
The fix is a pattern worth internalizing: carry the range of legal values down the recursion. Every node inherits an open interval (lo, hi) from its ancestors, checks that it fits, then hands each child a tighter interval. One pass, one comparison per node, no re-scanning.
The problem
A binary search tree requires that for every node, all values in its left subtree are strictly less than the node, and all values in its right subtree are strictly greater. Given the root of a binary tree, return true if it is a valid BST and false otherwise.
The catch is the word all. The constraint reaches past immediate children to every descendant.
Input: root = [5, 1, 4, null, null, 3, 6]
5
/ \
1 4
/ \
3 6
Output: false // 4 is the right child of 5 but 4 <= 5Node 4 sits directly under 5 on the right, so it must be greater than 5 — it isn't, so the whole tree is invalid. A checker that only compared 4 to its own children (3 and 6) would happily wave it through.
The brute force baseline
The correct-but-slow approach follows the definition literally. For each node, scan its entire left subtree to confirm every value is smaller, scan its entire right subtree to confirm every value is larger, then recurse into both children.
function isValidBST(root) {
if (!root) return true;
if (!allSmaller(root.left, root.val)) return false;
if (!allLarger(root.right, root.val)) return false;
return isValidBST(root.left) && isValidBST(root.right);
}
function allSmaller(node, val) {
if (!node) return true;
return node.val < val && allSmaller(node.left, val) && allSmaller(node.right, val);
}
function allLarger(node, val) {
if (!node) return true;
return node.val > val && allLarger(node.left, val) && allLarger(node.right, val);
}This is right, but it re-reads the same nodes over and over. Every node triggers a full walk of both its subtrees, and those nodes get walked again when their own ancestors are processed. On a skewed tree that's O(n²) — a node near the root re-scans nearly the entire tree. We're recomputing "is everything below me in range" from scratch at every level.
The key insight: inherit a range, don't re-scan
Instead of asking each node to survey its descendants, flip it: let each node inherit the exact window of values it's allowed to hold, decided entirely by the ancestors above it.
The root can be anything, so it starts with the widest possible interval (null, null) — unbounded on both sides. Then the rule for descending is mechanical:
- Turn left and the current node becomes a new upper bound. Everything left of it must be smaller, so pass the child
(lo, node.val). - Turn right and the current node becomes a new lower bound. Everything right of it must be larger, so pass the child
(node.val, hi).
Now consider the tree that fools naive checkers: root 10, right child 15, and 15's left child 6. The 6 is smaller than its parent 15, so a parent-only check passes it. But 6 lives in the right subtree of 10, so it inherited the lower bound 10. Its window is (10, 15), and 6 <= 10 — rejected. The bound set three levels up is exactly what catches it. That's the whole trick: an ancestor's value travels down as a constraint, so no node can quietly violate a rule set far above it.
The optimal solution
Each call receives the node plus its inherited lo and hi. It returns immediately on a null child, rejects the moment a value escapes its interval, and otherwise recurses with tightened bounds for each side.
var isValidBST = function(curr, lo = null, hi = null) {
if (!curr) return true;
if ((lo !== null && curr.val <= lo) || (hi !== null && curr.val >= hi))
return false;
let isLeftBST = isValidBST(curr.left, lo, curr.val);
let isRightBST = isValidBST(curr.right, curr.val, hi);
return isLeftBST && isRightBST;
}Three things carry the weight. The comparisons are strict (<= and >= both reject) because BSTs forbid duplicates across the ordering. The bounds are open intervals — null means "unconstrained on that side," which is why the root passes with no ancestors. And the final return isLeftBST && isRightBST short-circuits: the instant any node returns false, its parents propagate the failure up without visiting the rest of the tree.
Walkthrough
Trace the balanced tree [10, 5, 15, 3, 7, 12, 20]. Recursion goes left-first, so nodes are visited in the order 10, 5, 3, 7, 15, 12, 20. Each row is one node's bounds test.
| Node | lo | hi | Test | Verdict |
|---|---|---|---|---|
| 10 | null | null | unconstrained | pass |
| 5 | null | 10 | 5 < 10 | pass |
| 3 | null | 5 | 3 < 5 | pass |
| 7 | 5 | 10 | 5 < 7 < 10 | pass |
| 15 | 10 | null | 15 > 10 | pass |
| 12 | 10 | 15 | 10 < 12 < 15 | pass |
| 20 | 15 | null | 20 > 15 | pass |
Watch node 7: it inherited lo = 5 (it's in the right subtree of 5) and hi = 10 (it's in the left subtree of 10). Both bounds are active, and 7 threads the needle. Node 12 is the mirror case with window (10, 15). Those two-sided windows are precisely what a "compare to parent only" approach never builds. All seven nodes fit, so the answer is true.
Now swap in the invalid [5, 1, 4, null, null, 3, 6]. The recursion validates 5, then 1 and its null leaves, then reaches 4 with inherited bounds (5, null). 4 <= 5 fails, the call returns false, and the recursion unwinds without ever inspecting 3 or 6. That early exit is the short-circuit paying off.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Subtree re-scan | O(n²) | O(h) | each node re-walks both its subtrees |
| Recursive bounds | O(n) | O(h) | one comparison per node, single pass |
The bounds method visits each node exactly once and does O(1) work there, giving O(n) time. Space is the recursion stack, which reaches depth h — the tree's height. That's O(log n) for a balanced tree and O(n) for a fully skewed one. The re-scan baseline shares the same stack depth but pays O(n²) in time because it recomputes subtree membership at every level.
Common mistakes
- Comparing only to direct children. Checking
node.val > node.left.val && node.val < node.right.valmisses violations that live deeper. The6-under-15-under-10tree passes this check and is still not a BST. - Using
<where you need<=. BSTs reject equal values across the ordering. If your comparison is non-strict, a duplicate like a second5sitting where a larger value belongs slips through. - Seeding bounds with
Infinityand-Infinityin languages with fixed-width ints. Node values can equal the integer min/max. Thenull-means-unbounded convention here sidesteps that entirely — there's no sentinel a real value can collide with. - Passing the child's own value as the new bound. The bound is always the current node's value, not the child's. Left children inherit
(lo, curr.val); right children inherit(curr.val, hi). Swapping those silently accepts invalid trees.
Where this pattern shows up next
Carrying BST bounds and ordering down a recursion is the foundation for the rest of the BST toolkit:
- Search in a Binary Search Tree — the same left-or-right decision, but to find a value instead of validating one.
- Insert into a Binary Search Tree — walk the ordering down to the empty slot where a new node belongs.
- Kth Smallest Element in a BST — an inorder traversal turns a BST's structure into sorted order.
- Lowest Common Ancestor of a Binary Search Tree — split on the ordering to locate where two nodes diverge.
You can also step through Validate Binary Search Tree interactively to watch the (lo, hi) window tighten node by node and see the reject fire the instant a value escapes it.
FAQ
Why isn't it enough to compare each node to its children?
Because the BST rule applies to every descendant, not just immediate children. A node can be perfectly ordered relative to its own two children yet violate a bound set by a grandparent or higher. The tree with 10 at the root, 15 on the right, and 6 under 15 is the standard counterexample: 6 < 15 satisfies the local check, but 6 sits in the right subtree of 10 and must exceed 10. Only a method that carries the ancestor's bound down catches it.
What is the time and space complexity of the bounds solution?
Time is O(n) because each node is visited once and does a constant-time bounds comparison. Space is O(h), where h is the tree's height, from the recursion stack — O(log n) for a balanced tree and O(n) for a completely skewed one. The correct-but-naive subtree re-scan is O(n²) time since it re-walks both subtrees at every node.
Why are the comparisons strict (<= and >= both reject)?
A valid BST has no duplicate values across its ordering — the left subtree is strictly less and the right subtree is strictly greater. Using < and > for the bounds means a value equal to a bound is rejected. If you loosened them to <=/>= on the pass condition, a node equal to an ancestor's value would sneak through and you'd accept a tree that isn't a valid BST under the strict definition.
Can I validate a BST without recursion?
Yes. An inorder traversal of a valid BST yields values in strictly increasing order, so you can walk the tree inorder (iteratively with an explicit stack) and confirm each value is greater than the previous one. It's also O(n) time and needs the same O(h) stack space. The recursive bounds approach is usually cleaner to write and short-circuits on the first violation without tracking a "previous value" pointer.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.