Balanced Binary Tree

Lowest Common Ancestor of a Binary Tree

Spiral Matrix II

Determine whether every node's left and right subtree heights differ by at most one.

Given the `root` of a binary tree, return `true` if the tree is height-balanced, or `false` otherwise.

A binary tree is height-balanced when, for every node, the heights of its left and right subtrees differ by no more than `1`.

**Input / output**
- Input: `root: TreeNode` (JSON test fixture is a LeetCode-style level-order array using `null` for missing children, for example `[3,9,20,null,null,15,7]`)
- Output: `boolean`

**Examples**
1. `root = [3,9,20,null,null,15,7]` returns `true`.
2. `root = [1,2,2,3,3,null,null,4,4]` returns `false`.
3. `root = []` returns `true` because an empty tree is balanced.

**Constraints**
- `0 <= number of nodes <= 5000`
- `-10^4 <= Node.val <= 10^4`

**Follow-up**
Can you compute balance and height in the same postorder traversal so you never recompute subtree heights twice?

- Balance is a local rule that must hold at every node, not just at the root.
- That means we need subtree heights, but we also need to know whether a deeper subtree has already failed.

Understand the balance condition

- For each node, compute the height of the left subtree and the right subtree, compare them, then recurse into both children.
- This is correct, but repeated height work can make it `O(n^2)` on skewed trees.

Brute-force by recomputing heights

- A postorder traversal naturally computes child heights before the parent.
- If either child is already unbalanced, bubble up a sentinel like `-1` immediately instead of continuing normal height math.

Return a sentinel when a subtree is already unbalanced

- Return the subtree height when everything below the node is balanced.
- Return `-1` as soon as a node fails the balance check.
- The tree is balanced exactly when the root does not return `-1`.

Combine height and balance in one DFS

Trace `root = [1,2,2,3,3,null,null,4,4]`.

| node | left height | right height | return value |
|---|---:|---:|---:|
| leaf `4` | 0 | 0 | 1 |
| leaf `4` | 0 | 0 | 1 |
| node `3` (left subtree) | 1 | 1 | 2 |
| node `3` (right child of left subtree) | 0 | 0 | 1 |
| node `2` (left child of root) | 2 | 1 | 3 |
| node `2` (right child of root) | 0 | 0 | 1 |
| root `1` | 3 | 1 | `-1` (unbalanced) |

Dry run / postorder trace

- Computing height separately at every node, which degrades to `O(n^2)`.
- Treating an empty tree as unbalanced when it should return `true`.
- Forgetting that a subtree already marked unbalanced should short-circuit immediately.
- Follow-up: how would you implement the same idea iteratively with an explicit postorder stack?

Common mistakes and follow-ups

- `[]` and `[1]` are both balanced.
- A chain of three nodes is unbalanced at the root.
- Perfect trees are balanced at every level.
- A tree can look balanced at the root but still fail deeper down, so every subtree must be checked.

Edge cases to test mentally

A single postorder DFS returns each subtree height once and uses `-1` as an imbalance sentinel. Time is `O(n)`, and extra stack space is `O(h)` where `h` is the tree height.