Validate Binary Search Tree
Difficulty: Medium
Problem
Decide whether the binary tree rooted at root is a valid binary search tree (BST). For every node, ALL values in its left subtree must be strictly LESS than the node and ALL values in its right subtree strictly GREATER, and each subtree must itself follow the same rule. Checking only a node's immediate children is the classic mistake.
Example
Input: root = [5,4,6,null,null,3,7]
Output: false
Explanation: Node 3 looks fine next to its parent 6 (3 < 6 ✓). But 3 sits inside 5's RIGHT subtree, where everything must be GREATER than 5, and 3 isn't. Not a BST.Brute-force approach
The tempting check (each node against its parent only) is not a slower solution but a wrong one: it accepts [5,4,6,null,null,3,7]. The honest brute force is the audit: every node checks that its whole left subtree is smaller and its whole right subtree is bigger. It is correct but re-checks values again and again: 10 comparisons on a sorted chain of 5 nodes, 499,500 on a chain of 1,000 (n(n - 1) / 2), against one check per node for the range version.
Steps
- For every node, sweep its whole left subtree: every value must be smaller than the node
- Sweep its whole right subtree: every value must be bigger than the node
- Repeat for every node in the tree
- Return true only if no sweep finds a violation
Time complexity: O(n^2) on a chain (O(n log n) on a balanced tree) · Space complexity: O(h)
Trade-offs
- Every ancestor re-checks every descendant: 499,500 comparisons for a valid sorted chain of 1,000 nodes
- Re-derives facts an earlier visit already knew; the range version carries them down instead
Optimal approach
Key insight: Every turn you take on the way down leaves a promise. The (lo, hi) range remembers ALL of them. One comparison per node checks every ancestor at once.
Pass an allowed (lo, hi) range down the tree. Each node must sit strictly inside its range; going left tightens the ceiling, going right raises the floor.
Steps
- Start at the root with the wide-open range (-∞, +∞)
- At each node check: lo < node.val < hi; if not, return false
- Recurse left with (lo, node.val), the ceiling drops
- Recurse right with (node.val, hi), the floor rises
- Null subtrees are valid (they break no promises)
Time complexity: O(n) · Space complexity: O(h) where h = height of tree
Pseudocode
function isValidBST(root):
function check(node, lo, hi):
if node is null:
return ____
if not (____ < node.val < ____):
return false
return check(node.left, lo, ____) and
check(node.right, ____, hi)
return check(root, ____, ____)Hints
- An empty subtree contains no values, can it break any promise?
- The node must sit strictly INSIDE its inherited range, which two bounds?
- Going left, the CEILING becomes this node's value; going right, the FLOOR does
- The root has no ancestors. Start with the widest possible range
Complexity questions
What is the time complexity of the range-narrowing solution?
O(n): every node is checked exactly once against its range. Each node does one O(1) range comparison and hands narrowed ranges to its children. One traversal → O(n).
What is the space complexity?
O(h): the recursion stack, each frame holding two numbers. Only the recursion stack: O(log n) balanced, O(n) skewed. The two range numbers per frame are constant space.
Why does 'the inorder traversal comes out strictly increasing' also prove a valid BST?
Inorder visits left-subtree, node, right-subtree, in a BST that's smallest to largest, so any violation shows up as a non-increasing adjacent pair. Inorder on a BST produces sorted output (you learned this in the traversals lessons!). The converse holds too: if inorder is strictly increasing, the BST property holds everywhere. Same O(n), different style.
Why does [1,1] (root 1 with left child 1) fail validation?
The inequalities are STRICT: the left child must be < its ancestor, and 1 < 1 is false. The left child inherits range (-∞, 1) and must satisfy val < 1. A duplicate 1 fails. Under this problem's definition, equal values anywhere in a subtree make the tree invalid.
Check your understanding of Validate Binary Search Tree
What exactly does the BST property require?
The ENTIRE left subtree < node < the ENTIRE right subtree, at every node. It's about whole subtrees, not just direct children. Every single value anywhere in the left subtree must be smaller; every value in the right subtree must be greater. The immediate-children version is the famous WRONG answer.
In [5,4,6,null,null,3,7], node 3 satisfies 3 < 6 with its parent. Why is the tree still invalid?
Because 3 lives inside 5's RIGHT subtree, so it must be GREATER than 5: ancestors' rules reach all the way down. When we turned RIGHT at 5, we promised: everything below is > 5. Node 3 breaks that promise made two levels up. Parent-child checks alone can never catch this.
How can we carry EVERY ancestor's constraint using just two numbers?
An allowed open range (lo, hi): the node must satisfy lo < val < hi. Each turn on the way down narrows the range. By the time we reach any node, (lo, hi) summarizes every promise made above it. One comparison checks them all at once.
Going LEFT from a node with value v, how does the child's allowed range change?
The ceiling drops: (lo, v), everything left of v must be smaller than v. Turning left promises 'smaller than v', so the ceiling tightens to v: (lo, v). Symmetrically, turning right raises the floor: (v, hi).
What range does the root start with?
(-∞, +∞): no promises made yet. The root has no ancestors, so nothing constrains it: any value is allowed. Constraints only accumulate as we descend and turn.