Validate Binary Search Tree
Validate Binary Search Tree: is the tree a valid BST? Every node must exceed ALL left descendants and be below ALL right ones.
- The number of nodes in the tree is in the range [1, 10⁴].
- -2³¹ <= Node.val <= 2³¹ - 1
Intuition
To validate binary search tree structure, every node must be greater than all values in its left subtree and less than all values in its right — not merely greater than its left child and less than its right child.
That distinction is the entire problem, and the local check is the classic wrong answer. Consider the tree [5, 4, 6, null, null, 3, 7]. Node 6 has children 3 and 7, so it passes a local test. But 3 sits in the right subtree of 5 while being smaller than 5, which violates the BST property. A parent-versus-children check never looks far enough to catch it.
What a node really needs is the constraint imposed by every ancestor at once, and that collapses neatly into a range:
- Each node must lie strictly between a lower and an upper bound inherited from above.
Descending into a left child tightens the upper bound to the parent's value; descending right raises the lower bound to it. The root starts unbounded. So a node deep in the tree carries the accumulated constraint of every ancestor without needing to know any of them individually — in the example, node 3 arrives with a lower bound of 5 and fails immediately.
An alternative uses the fact that a BST's inorder traversal is strictly increasing: walk it and confirm each value exceeds the previous one. Same O(n), different bookkeeping.
BST validity is a range property, not a local one, so the pattern is to push an allowed interval down the recursion rather than compare neighbours. Going left tightens the upper bound to the current value; going right raises the lower bound. Any time a subtree's legality depends on ancestors it never sees directly, thread the constraint down as an argument — that's the same trick behind recover-BST and range-sum queries.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Reject the local-comparison approach
Checking left.val < node.val < right.val at each node misses violations between a node and a distant ancestor. In [5,4,6,null,null,3,7] the value 3 passes locally under 6 while breaking the property against 5 — this counterexample is worth remembering.
Carry a range down the recursion
Define valid(node, low, high) requiring low < node.val < high. The root is called with infinite bounds. The range is the compressed form of every ancestor constraint, which is why one comparison at each node suffices.
Tighten the bound on each descent
Recurse left with high = node.val, since everything there must stay below this node. Recurse right with low = node.val. Each step narrows the window, and a node that falls outside its window fails immediately.
Use strict comparisons
Both bounds are exclusive: duplicates are not allowed in a valid BST under this problem's definition. Using <= anywhere accepts trees with equal keys, which is a subtle wrong answer that passes most casual test cases.
Consider the inorder alternative
A BST's inorder traversal is strictly increasing. Traverse while keeping the previously visited value and confirm each new one is larger. Same O(n) cost; the only trap is remembering the previous value across recursive calls rather than resetting it.
Cost of the validation
Every node is visited once and compared against two bounds, giving O(n) time. Space is O(h) for the recursion stack — O(log n) when balanced, O(n) on a degenerate chain.
Solution & live demo
Common pitfalls
Comparing each node only with its direct children
if node.left and node.left.val >= node.val: return False if node.right and node.right.val <= node.val: return False return valid(node.left) and valid(node.right)
def valid(node, lo, hi):
if not (lo < node.val < hi): return False
return valid(node.left, lo, node.val) and valid(node.right, node.val, hi)This is the classic wrong answer. Take root 5 with left child 1 and 1's right child 6: every parent-child pair is fine locally, yet 6 sits in the left subtree of 5 and must be under 5. A node is constrained by every ancestor above it, not just its parent.
Using <= and admitting duplicates
if not (lo <= node.val <= hi): return False
if not (lo < node.val < hi): return False
LeetCode's definition requires strictly smaller on the left and strictly larger on the right, so equal values are invalid. Loosening the comparison accepts a tree with duplicated keys.
Seeding the bounds with integer limits
return valid(root, -2**31, 2**31 - 1)
return valid(root, float("-inf"), float("inf"))A single-node tree holding exactly -2147483648 is a valid BST, but a non-strict-safe integer bound rejects it. Infinities can never collide with real input values.
Edge cases
Strict inequalities reject equality — duplicates invalidate.
±∞ initial bounds avoid sentinel-value collisions.