STEP 14 · BINARY SEARCH TREES · VERDICT AND EVIDENCE TRAVEL TOGETHER · HARD

Largest BST Subtree in a Binary Tree

WHAT IT SAYS

In an arbitrary binary tree, find the size of the largest subtree that is itself a valid BST.

WHAT IT'S REALLY ASKING

"Whether I'M a BST is decided by four facts about my children: are you each a BST, and what are your extreme values? If both say yes and left's max stays under me and right's min stays above me — I qualify, and my size is theirs plus one. Everything needed flows upward in one bundle. The question was never 'check each subtree'; it was 'make each subtree testify once.'"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Validate every subtree independently

O(n^2) time on skewed trees — n validations, each up to O(subtree)

For each node in the tree, run a full BST validation on its subtree (range check or inorder monotonicity); if valid, count its nodes; track the largest count seen.

WHERE THE WORK IS WASTED — This is the balanced-tree disease at its worst, because the redundancy is layered: a node at depth d has its subtree re-validated by all d of its ancestors' checks, so deep nodes are re-examined once per ancestor — the sum-of-depths bill, quadratic on a spine. And the repeat work is PURE repetition: whether a subtree is a BST, and what its min and max are, never changes between the checks. The validation of a parent recomputes from scratch four facts its children's validations already established and threw away. The helper-inside-recursion signature — a full traversal launched at every node of another traversal — is the exact structural smell Balanced Binary Tree taught you to distrust.

KEY OBSERVATION — THE UNLOCKlink

Four numbers from each child settle the parent completely.

Ask precisely what a node needs from below to render its own verdict. It needs: is my left subtree a BST, is my right subtree a BST, what is the left subtree's MAXIMUM (to compare against my value), and the right subtree's MINIMUM. Nothing else — the invariant 'everything left is smaller, everything right is larger' compresses each side's entire population into one extreme value, because if the maximum of the left clears the bar, everything under it does too. So the recursive contract is a tuple: (isBST, min, max, size). If it holds for the children, the parent computes its own tuple in O(1): valid iff both children valid AND left.max < my value < right.min; my min is left's min (or my value if no left child); my max is right's max symmetrically; my size is left.size + right.size + 1. Every node computes its tuple exactly once, in post-order, from its children's tuples — no re-descent ever. A running global maximum harvests the size from every node whose tuple says valid. O(n) total, and the quadratic disease is cured by the same medicine as Balanced Binary Tree: fuse the verdict into the computation that was already visiting everyone, and make the return value carry ALL the evidence the parent will need — not just the boolean. Two details are where implementations die. First, the failure convention: when a subtree is NOT a BST, its min/max are meaningless — but ancestors will still read them. Either carry the explicit boolean (safest), or poison the extremes (return min = -∞, max = +∞ from invalid subtrees, which automatically fails every ancestor's comparison — elegant, but document it). Second, the null base case must be the IDENTITY of the combination: (valid, min = +∞, max = -∞, size 0), the infinities chosen so a missing child never constrains its parent. Get the null tuple wrong and every leaf misvalidates. Note what this problem really is: Validate BST, upgraded from a global yes/no into a per-node census — and the upgrade forced the return value to grow from a boolean into a struct. That growth is the general move: when ancestors need more than a verdict, widen the contract until the evidence travels with it.

One post-order pass returning (valid, min, max, size)

O(n) time — one visit per node — O(h) stack space

Recurse: null returns (true, +∞, -∞, 0). Get both children's tuples; the node is valid iff both are and left.max < val < right.min. Return (valid, min(left.min, val), max(right.max, val), left.size + right.size + 1) when valid — updating the global best with the size — else return an invalid marker (or poisoned extremes). The global best after the root's call is the answer.

WHAT YOU TRADED — The widened return tuple is the whole cost: four fields to keep coherent, a null-identity to get exactly right, and a failure convention to choose — in exchange, n independent validations collapse into one pass. Note the poisoned-extremes trick trades explicitness for compactness; in interview conditions the explicit boolean is cheaper to defend. The transferable lesson: when a per-node question depends on subtree-wide facts, don't re-derive the facts per node — widen the post-order contract until each subtree testifies once, completely.

WATCH THE IDEA RUN

each child reports isBst · min · max · size

largest BST 0

The naive version asks, at every node, 'is my whole subtree a BST?' — and answering that re-walks the subtree. The same nodes get validated over and over. The fix is to widen what a child is required to report.

step 1 / 8

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Widen the Contract Until Evidence Travels

YOU'LL SEE IT AGAIN WHEN

Every node asks a question whose answer needs subtree-wide aggregates (extremes, sizes, validity) — and a helper-inside-recursion is recomputing them per ancestor.
The aggregates compose in O(1): the parent's facts are a fixed formula over the children's facts, so one post-order pass suffices.
Null children must return the combination's identity element (±∞ extremes, zero size) or every leaf's verdict is wrong.

SAME BLUEPRINT, DIFFERENT PROBLEM

Validate Binary Search Tree (the boolean-only ancestor of this contract)Balanced Binary Tree (the same fusion cure, smaller payload)Binary Tree Maximum Path Sum (another widened post-order contract)Count BST Nodes in Range

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