99. Balanced Binary Tree

Compute each subtree's height once, bottom-up. As soon as any subtree is unbalanced, propagate a sentinel (-1) upward so the whole tree short-circuits to unbalanced.

One pass, not two

A naive check computes height at every node and re-walks the subtree — O(n²). Instead, fold the balance check into the height computation: a helper returns the real height, or -1 the moment it discovers imbalance. Once -1 appears it bubbles up unchanged.

Walk-through

height(node):
    if node is None: return 0
    lh = height(node.left);  if lh == -1: return -1
    rh = height(node.right); if rh == -1: return -1
    if abs(lh - rh) > 1: return -1
    return 1 + max(lh, rh)
return height(root) != -1

Worked example

[3,9,20,null,null,15,7]:

• 9 → height 1, 15 → 1, 7 → 1, 20 → 2.
• At root 3: left height 1, right height 2, |1-2| = 1 ≤ 1 → balanced → return true.

Complexity

• Time: O(n) — each node visited once.
• Space: O(h) recursion stack.

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        int lh = height(node.left);
        if (lh == -1) return -1;
        int rh = height(node.right);
        if (rh == -1) return -1;
        if (Math.abs(lh - rh) > 1) return -1;
        return 1 + Math.max(lh, rh);
    }
}