4.14.4 — Balanced Binary Tree

LeetCode 110 · Easy

The problem

Return true if the tree is height-balanced: for every node, the depths of its two subtrees differ by at most 1.

     3
   /   \
  9    20        →  true
      /   \
    15     7

       1
     /   \
    2     2      →  false   (the left side is 2 deeper than the right)
   / \
  3   3
 / \
4   4

The obvious solution, and its cost

Write isBalanced(node) as: check this node's two depths differ by at most 1, then recurse into both children.

That is correct and it is O(n^2), because computing the depth at every node rewalks its whole subtree. On a degenerate tree, the top node's depth check walks n nodes, the next walks n−1, and so on.

Name the waste: the depth of a subtree is computed once per ancestor, when one computation would do.

The pattern

Compute the depth once per node, and use the same pass to detect imbalance. This is the return one thing, record another structure from 4.14.3, with a twist: instead of a side variable, you can fold the failure into the return value using a sentinel.

Return the depth normally. Return -1 to mean "something below here is unbalanced". Since a real depth is never negative, -1 cannot be confused with a valid answer, and it propagates straight to the top.

The solution

Python

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def depth(node) -> int:
            if not node:
                return 0

            left = depth(node.left)
            if left == -1:
                return -1                    # already broken below — stop

            right = depth(node.right)
            if right == -1:
                return -1

            if abs(left - right) > 1:
                return -1                    # broken here

            return 1 + max(left, right)

        return depth(root) != -1

TypeScript

function isBalanced(root: TreeNode | null): boolean {
  function depth(node: TreeNode | null): number {
    if (!node) return 0;

    const left = depth(node.left);
    if (left === -1) return -1;

    const right = depth(node.right);
    if (right === -1) return -1;

    if (Math.abs(left - right) > 1) return -1;

    return 1 + Math.max(left, right);
  }

  return depth(root) !== -1;
}

The early -1 checks are what make it fast. Once any subtree reports failure, no further work happens anywhere — the -1 short-circuits up through every ancestor. Checking left before even calling depth(node.right) means an unbalanced left subtree stops the right one from being walked at all.

A sentinel works here because the value space has room. Depths are always ≥ 0, so −1 is unmistakable. When no such spare value exists, use a side variable instead, as in 4.14.3. Both are fine; pick whichever is cleaner for the value type.

An alternative that some people prefer is returning a pair (depth, is_balanced). It is more explicit and slightly more code. If the sentinel feels like a trick to you, use the pair — the interviewer cares that you compute each depth once, not which encoding you chose.

Complexity

O(n) time — each node's depth is computed exactly once. O(h) space.

That is the whole point of the problem: turning the obvious O(n^2) into O(n) by not recomputing.

What "balanced" actually buys

The definition — every node's subtree depths within 1 — is what an AVL tree enforces, and it is why AVL trees guarantee O(\log n) operations. An unbalanced binary search tree can degenerate into a linked list, and then every lookup is O(n).

4.13.2 covers how rotations restore this property after an insertion, and why red-black trees use a looser rule that is cheaper to maintain.

Where this goes next

• Maximum Depth — the same recursion without the check. 4.14.2.
• Diameter — same shape, side variable instead of a sentinel. 4.14.3.
• Validate Binary Search Tree — a different property checked on the same single pass. 4.14.11.

The rule: when a check at every node needs a value computed from its subtree, compute the value once on the way up and fold the check into the same pass.

What the interviewer will push on

"Why is the naive version O(n^2)?" Each subtree's depth is recomputed once per ancestor.

"How do you avoid it?" One post-order pass computing each depth once, with the failure carried in the return value.

"Why is -1 safe as a sentinel?" Depths are never negative.

"What does balanced mean here, exactly?" Every node, not just the root. The second example in the problem statement fails only at a lower node.

One thing to volunteer: mention AVL trees. This definition is not arbitrary — it is the invariant a self-balancing tree maintains, and knowing that connects the exercise to something real.

Next: 4.14.5 Same Tree — comparing two trees at once, which is the building block for the problem after it.