STEP 14 · BINARY SEARCH TREES · THE CONSTRAINT IS INHERITED, NOT LOCAL · MEDIUM

Validate Binary Search Tree

WHAT IT SAYS

Decide whether a binary tree satisfies the BST property: every node exceeds everything in its left subtree and is exceeded by everything in its right subtree.

WHAT IT'S REALLY ASKING

"The classic wrong answer checks each node against its two children — and passes trees where a grandchild violates a grandparent. The property is not between parent and child; it is between a node and EVERY ancestor. The saving grace: all those ancestral demands compress into just two numbers — a floor and a ceiling — handed down the tree."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Check every node against its immediate children

O(n) time — and WRONG, which is worse than slow

Traverse the tree; at each node verify left child's value is smaller and right child's is larger. If every local check passes, declare the tree valid.

WHERE THE WORK IS WASTED — This isn't waste; it's a counterexample factory. Take root 10, left child 5, and give 5 a right child of 12. Every parent-child pair passes: 5 < 10, 12 > 5. But 12 sits in 10's LEFT subtree, where everything must be under 10. The bug is a misreading of the invariant: 'left child smaller' is a two-node statement, while the BST property is a statement about entire subtrees — the node constrains its grandchildren, great-grandchildren, all descendants on each side. Local checks verify a strictly weaker property, and weaker properties admit impostors.

KEY OBSERVATION — THE UNLOCKlink

Every ancestor's demand compresses into one floor and one ceiling.

Ask what the tree's structure has promised about a node before you even read its value. Each LEFT turn on the path from the root imposed a ceiling — you entered a subtree where everything must stay below that ancestor. Each RIGHT turn imposed a floor. A node deep in the tree carries the full stack of these obligations. Here is the compression that makes the problem linear: among all the ceilings, only the TIGHTEST binds — satisfy the smallest ceiling and you satisfy them all, because later left turns always tighten (you turned left from a node already under the old ceiling). Same for floors. So the unbounded set of ancestral constraints collapses to exactly two numbers: the interval (lo, hi) the current node's value must fall in. And the interval updates in O(1) per step, which is what makes it a recursion parameter rather than a recomputation: descending left keeps lo and shrinks hi to the current value; descending right keeps hi and raises lo. Root starts unbounded. Validity is then one comparison per node — lo < val < hi — and the strictness of those comparisons is where duplicate policy lives (LeetCode demands strict; know your contract). The second route deserves its own paragraph because it is a different worldview: a tree is a BST if and only if its inorder traversal is strictly increasing. Proof sketch: inorder emits left, node, right; if the sequence ever descends, some node preceded a smaller one, violating the subtree ordering somewhere on their shared ancestry; conversely a valid BST's inorder is sorted by the argument in the k-th smallest problem. Checking 'strictly increasing' needs only the PREVIOUS emitted value — one variable, no array. Same O(n), and it doubles as the mental model for Recover BST, where the inorder stream's descents literally point at the corrupted nodes. Two routes, one lesson: a global property became checkable locally only after finding the right summary of the past — an interval in one framing, a single predecessor in the other.

Range recursion, or inorder with a trailing previous

O(n) time — every node once — O(h) stack either way

Range version: validate(node, lo, hi) — null is true; fail if val ≤ lo or val ≥ hi; recurse left with (lo, val) and right with (val, hi). Use sentinel infinities or nullable bounds to dodge integer-limit edge cases. Inorder version: walk inorder carrying prev; fail the moment a visit does not strictly exceed prev.

WHAT YOU TRADED — The range version short-circuits on the first violation along ANY path and never needs the notion of a traversal order; the inorder version is fewer moving parts but subtly stateful (the prev variable threads through the recursion) and hands you the Recover-BST toolkit for free. Both beat the broken local check by verifying the actual invariant. The transferable lesson: when a property relates each element to ALL its ancestors, look for the compressed summary of the ancestry — often an interval, a max-so-far, or a single predecessor — and pass it down instead of re-deriving it.

WATCH THE IDEA RUN

labels are (floor, ceiling) inherited from ALL ancestors

children-only check says valid — and it is wrong

Check each node against its own two children and this tree passes every test: 4 is bigger than 3, 4 is smaller than 6, 5 is bigger than 1. And it is still not a BST. Being a BST is not a local property.

step 1 / 8

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Compress the Ancestry Into Bounds

YOU'LL SEE IT AGAIN WHEN

The invariant relates a node to its entire ancestor path, so any fixed-radius local check verifies a strictly weaker property.
Ancestral constraints are monotone — later ones only tighten — so the whole set collapses to a running floor and ceiling.
Equivalently, the structure's canonical traversal linearises the invariant into 'monotone stream', checkable with one trailing value.

SAME BLUEPRINT, DIFFERENT PROBLEM

Recover Binary Search TreeLargest BST SubtreeKth Smallest Element in a BST (the same inorder stream)Maximum Depth (contrast: a genuinely local property, where child checks suffice)

The bar isn't "solved it once." It's "could rebuild it from the observation."