STEP 13 · BINARY TREES · ANSWER BOTH QUESTIONS IN ONE PASS · EASY

Balanced Binary Tree

WHAT IT SAYS

Decide whether a binary tree is height-balanced: at every node, the two subtree heights differ by at most one.

WHAT IT'S REALLY ASKING

"To check balance you need heights, and computing a height already visits every node underneath. So the real question is: why are 'what is your height?' and 'are you balanced?' two separate journeys, when the second is a one-comparison byproduct of the first?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

At every node, compute both heights and compare

O(n log n) on a balanced tree, O(n^2) on a skewed one

Write a height() helper. Then, for each node, call height(left) and height(right), check the difference, and recurse the balance-check into both children.

WHERE THE WORK IS WASTED — Count how often a single deep node gets visited. height() called from the root walks down to it. Then the balance check recurses one level and calls height() again — which walks down to it again. Every node is re-measured once for every ancestor it has, so the total work is the sum of all depths. The heights you are recomputing did not change between calls; nothing changed. You are re-deriving a stable fact from scratch at every level of the tree, purely because your height function throws the answer away instead of handing it upward.

KEY OBSERVATION — THE UNLOCKlink

The height computation already visited everyone — make it testify.

The post-order height recursion touches every node exactly once, and at the moment it stands at a node it is holding exactly the two numbers the balance check needs: the left height and the right height. The check is one subtraction. Refusing to do it there, and instead launching a second traversal later, is the entire inefficiency. So fuse the two questions into one return value. The subtlety is that the fused function must report two things — a height (a number) and balancedness (a boolean) — and there are two clean ways to do it. The sentinel trick: return the height normally, but return -1 to mean 'something below me is broken'. This works because heights are never negative, so -1 is unclaimable by any real answer — the error value lives outside the codomain. And brokenness propagates correctly for free: if either child reports -1, report -1 immediately without even computing; if the local difference exceeds 1, report -1; otherwise report the real height. Notice the short-circuit is not an optimisation bolted on — it is the observation that imbalance anywhere makes every ancestor's height irrelevant. The honest-pair version returns (height, isBalanced) explicitly. Same information, no magic number, slightly more ceremony. Choose by taste; the structure is identical. The general principle is worth stating because it recurs constantly: when checking property P requires computing quantity Q, and computing Q traverses the whole structure anyway, do not check P separately — smuggle P's verdict into Q's return value.

One post-order pass with a sentinel

O(n) time — each node visited once — O(h) stack space

Recurse: null returns 0. Get the left result; if it is -1, return -1. Get the right result; if it is -1, return -1. If the heights differ by more than one, return -1. Otherwise return 1 plus the larger height. The tree is balanced exactly when the root's answer is not -1.

WHAT YOU TRADED — The sentinel overloads one number with two meanings, which is compact but fragile — it only works because -1 is outside the range of legal heights, and a reader must know the convention. The pair return is self-documenting at the cost of noise. Either way, the transferable lesson is the fusion itself: a validity check that needs a computed quantity should ride along with the computation, not re-run it — the same move powers validate-BST-via-min-max and diameter-via-height.

WATCH THE IDEA RUN

CALL STACK

stack empty — every branch explored

the return channel carries height, OR -1 = unbalanced

verdict pending

The naive version asks each node for its height, then asks AGAIN for every subtree — the same walk, run over and over. Watch this single walk carry both answers at once.

step 1 / 12

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Smuggle the Verdict in the Return Value

YOU'LL SEE IT AGAIN WHEN

Checking the property at one node requires a quantity (height, size, sum) whose computation already traverses the entire subtree.
The naive solution has a helper called inside a recursion, and the helper's cost is proportional to the subtree — the signature of accidental O(n^2).
Failure anywhere below invalidates everything above, so a propagating error value can short-circuit the rest of the walk.

SAME BLUEPRINT, DIFFERENT PROBLEM

Diameter of Binary TreeValidate Binary Search TreeMaximum Path SumLargest BST Subtree

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