110 · Balanced Binary Tree

The sentinel-abort idiom. One recursion returns two different kinds of thing through the same int: a real height, or −1 meaning "stop asking, this tree is already unbalanced." That single overloaded return is what turns an O(n log n) solution into an O(n) one.

1 — The problem

A tree is height-balanced when every node has left and right subtree heights differing by at most 1. The obvious reading of that sentence produces the obvious — and slow — solution:

The trick is recognising that the two questions — "how tall is this subtree?" and "is it balanced?" — can share one return channel, because the answer to the second is only ever needed as a veto. As soon as a veto exists, the height is irrelevant, so the height slot is free to carry the veto instead.

Sub-variant C solves the same tension by splitting the two answers apart: return one value, record the other in a field. Here they are compressed into a single integer. Both are worth having; C generalises further, this one is shorter.

2 — Watching −1 propagate

This tree is unbalanced at node 2: its left subtree is 2 tall and its right side is empty. Watch what happens to node 9 — the entire right half of the tree — once that violation is found.

Node 9 is never entered. The root calls left, receives −1 on line 4, and returns before line 5 is ever reached. That is not an optimisation bolted on afterwards — it falls out of putting the check between the two recursive calls rather than after both of them. Move line 4 below line 5 and the code is still correct, but it now walks the whole tree.

2.1 Why −1 is a safe sentinel

An overloaded return only works if the sentinel can never be produced legitimately. Heights here are counted in nodes, so a real height is always ≥ 0, and -1 is unreachable by the normal path. Two things follow:

• Do not switch to edge-counting in this problem. If null returns -1 so that leaves return 0, the sentinel collides with a real height and the recursion starts aborting on empty subtrees.
• The propagation checks are mandatory, not decorative. Drop line 4 and a −1 flows into Math.abs(L - R) as if it were a height, where it looks like a very short subtree — and can silently produce a balanced-looking answer.

When no such spare value exists — say the aggregate is an arbitrary int that could genuinely be −1 — you have outgrown this idiom. Return a small object, or use the record/return split of sub-variant C.

3 — Complexity and edge cases

• Time O(n), space O(h). Each node returns once and the sentinel short-circuits whole subtrees, so the true count is often well under n.
• Empty tree: balanced — height(null) is 0, never −1, and the wrapper reports true.
• Single node: balanced. |0 - 0| = 0.
• A node with one child that is a leaf is the boundary case: |1 - 0| = 1, which is allowed. Add one more level below that child and it becomes 2, which is not. If your code disagrees on that pair, the comparison is > 1 and not ≥ 1.
• Common bug: checking balance only at the root. A tree can have equal overall left and right heights and still be badly unbalanced two levels down — the definition is quantified over every node, which is exactly why the check lives inside the recursion rather than outside it.

4 — Reference implementation

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

private int height(TreeNode nd) {
    if (nd == null) return 0;
    int L = height(nd.left);
    if (L == -1) return -1;        // abort before touching the right subtree
    int R = height(nd.right);
    if (R == -1) return -1;
    if (Math.abs(L - R) > 1) return -1;
    return 1 + Math.max(L, R);   // identical to LC 104
}

Strip the three sentinel lines and what is left is LC 104 verbatim. That is the point of sub-variant A: the aggregation skeleton does not change, only what it is allowed to refuse.