Balanced Binary Tree: One Bottom-Up Pass Instead of N Height Checks

A binary tree is height-balanced when no node's two subtrees differ wildly in depth — the property that keeps operations on trees like AVL and red-black trees fast. The definition is simple, but the obvious way to check it does an enormous amount of repeated work.

The trap is that "measure the height of every node" and "check the balance of every node" feel like two separate jobs. Do them separately and you re-walk the same subtrees over and over, landing at O(n²). Fuse them into one pass and you get O(n) — the whole difference is which direction information flows.

This problem is the cleanest introduction to the bottom-up DFS idea: let recursion hand heights back up the call stack, and decide balance on the way up instead of the way down.

The problem#

Given the root of a binary tree, return true if the tree is height-balanced. A tree is height-balanced when, for every node, the heights of its left and right subtrees differ by at most 1.

The word every is the whole problem. A tree can look fine at the root and still be unbalanced three levels down.

For contrast, [1, 2, 2, 3, 3, null, null, 4, 4] is false: the left subtree keeps descending while the right stops early, so the root's two sides differ in height by 2.

The brute force baseline#

The direct translation of the definition: write a height function, then at every node compare the heights of its two children and recurse.

It's correct, but look at what height does: it walks an entire subtree just to return a number. Then isBalanced recurses into that same subtree and calls height again on all of its nodes. Every node gets its height recomputed once for each ancestor above it.

On a balanced tree that's O(n log n); on a skewed chain it degrades to O(n²) — for a 10⁴-node stick, a hundred million operations to answer a yes/no question. The information you need (subtree heights) is being thrown away and recomputed instead of reused.

The key insight: measure and check on the way up#

The wasted work comes from computing height top-down — asking a fresh height question at every node. Flip it. A single DFS that returns each subtree's height already has both child heights in hand at the exact moment it needs to check balance.

So do both jobs in one recursion:

• Recurse into left and right first — they return their heights.
• With both heights known, check |leftHeight - rightHeight| > 1. If it's violated, record that the tree isn't balanced.
• Return 1 + max(leftHeight, rightHeight) so the parent can measure itself.

This is bottom-up DFS: information (height) flows up the call stack, and the balance decision happens at each frame using values the children already returned. Every node is measured exactly once.

The visualizer teaches a clean version of this that keeps a single boolean flag in an outer closure rather than threading a sentinel value through return statements.

The optimal solution#

Three things make this work:

• ans lives outside the recursion. calculateHeight is only responsible for returning heights. Whenever any frame sees a difference greater than 1, it ANDs false into the closed-over ans. One violation anywhere permanently flips it.
• The height return is unconditional. Even after a frame flips ans, it still returns 1 + max(...). That matters: the parent still needs a real height to measure its own balance. The code never short-circuits the height math.
• Null is height 0. The if (!curr) return 0 base case means a missing child contributes 0, so a leaf returns 1 + max(0, 0) = 1.

At the end, ans is true only if no frame ever tripped the invariant.

Walkthrough#

Tracing root = [3, 9, 20, null, null, 15, 7]. Recursion descends left-first, so heights finalize in postorder — children before parents. Each row is the moment a calculateHeight frame returns.

Node 3 is the interesting row: its left side (just node 9) has height 1 and its right side (node 20's subtree) has height 2. The difference is exactly 1 — right at the boundary, still allowed. ans is never flipped, so isBalanced returns true.

Now picture the unbalanced input instead. Somewhere deep, a frame computes |2 - 0| = 2, runs ans = ans && false, and from that point no amount of later true values can recover it — ans && false is sticky. The recursion still finishes measuring every height, but the final return ans is false.

Complexity#

h is the tree height — the maximum depth of the recursion stack. That's O(log n) for a balanced tree and O(n) for a fully skewed one. Time is strictly O(n) because each node is visited once and does constant work: two child comparisons and a max.

Common mistakes#

• Recomputing height top-down. Calling a separate height() at every node is the O(n²) trap. Fuse height and balance into one pass — that's the entire point of the problem.
• Only checking the root. Balance must hold for every node. A tree can have a perfectly even root while a deep sub-subtree is lopsided. The recursion checks all of them precisely because it runs at every frame.
• Short-circuiting the height return. If a frame stops returning a real height after detecting imbalance, ancestor frames measure themselves with a wrong (or missing) value. Keep the height math unconditional; only the ans flag reacts to imbalance.
• Confusing height with depth. Height is measured up from the deepest leaf; a null child is 0 and a leaf is 1. Off-by-one here makes a balanced tree read as unbalanced at the boundary case (a diff of 1).
• Assuming balanced means complete. Height-balanced only bounds the height difference per node. It does not require the tree to be full or perfectly filled.

Where this pattern shows up next#

Bottom-up DFS — returning a value from each subtree and combining it at the parent — is the workhorse for tree problems. Once the recursion-returns-information reflex clicks here, these are natural next steps:

• Binary Tree Preorder Traversal — the recursive DFS skeleton this solution is built on, in its simplest visiting order.
• Binary Tree Inorder Traversal — the same recursion with the visit sandwiched between the two child calls.
• Binary Tree Preorder Traversal - Iterative — the explicit-stack version that makes the call stack you're relying on here visible.
• Binary Tree Inorder Traversal - Iterative — managing that stack by hand for the inorder order.

You can also step through Balanced Binary Tree interactively to watch heights fill in from the leaves up and the balance check fire at each node.

FAQ#

What does height-balanced actually mean?#

A binary tree is height-balanced when, for every single node, the heights of its left and right subtrees differ by at most 1. The keyword is every — the condition has to hold at the root and at every descendant, not just at the top. A tree can be perfectly even at the root and still fail the test because some deep node has one subtree two levels taller than the other.

Why is the optimal solution O(n) when the brute force is O(n²)?#

The brute force computes each node's height with a separate function that re-walks its entire subtree, and it does that at every node — so lower nodes get their heights recomputed once for every ancestor above them. The bottom-up version computes each subtree's height exactly once and reuses it: recursion returns the child heights, and the parent checks balance immediately with those values in hand. One measurement per node instead of one per node-ancestor pair collapses O(n²) into O(n).

Why does the code use an ans flag instead of returning early?#

The version taught here keeps calculateHeight focused on one job — returning a height — and records imbalance in a closed-over ans = ans && false flag. That keeps the height math unconditional, so every parent frame always gets a real height to measure itself with. A common alternative returns a sentinel -1 up the stack the moment imbalance is found, which lets the recursion bail early; both are O(n) and correct. The flag version trades early exit for simpler, side-effect-based bookkeeping.

What is the space complexity, and can it be O(n)?#

Space is O(h), where h is the height of the tree — the maximum depth of the recursion call stack. For a balanced tree that's O(log n), but for a fully skewed tree (a linked-list-shaped tree) the recursion goes n frames deep, so worst-case space is O(n). There's no extra data structure beyond the call stack itself and the single boolean flag.

Does an empty tree count as balanced?#

Yes. An empty tree (null root) is trivially height-balanced — there are no nodes whose subtrees could violate the invariant. In the code, calculateHeight(null) hits the if (!curr) return 0 base case immediately, ans is never touched, and the function returns its initial value of true.