Validate Binary Search Tree
Is the tree a valid BST? Every node must exceed ALL left descendants and be below ALL right ones.
Open on LeetCode ↗Intuition
Checking only parent vs children misses violations deep in a subtree. Carry (min, max) bounds down instead: entering a left child caps the max at the parent; a right child raises the min. Each node checks itself against bounds inherited from every ancestor at once.
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
The classic wrong answer
node.left.val < node.val < node.right.val locally is NOT enough — a grandchild can violate a grandparent (e.g. [5,4,6,null,null,3,7], the 3 under 6).
Bounds propagation
valid(node, lo, hi): require lo < node.val < hi; recurse left with hi=node.val, right with lo=node.val.
Alternative: inorder
A BST's inorder is strictly increasing; traverse and compare consecutive values — same O(n).
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.