The problem
Decide whether a binary tree is height-balanced: at every node, the heights of the two subtrees differ by at most 1.
Stuck? Reveal hints one at a time
How to approach it
- 1Write check(node): returns the height if the subtree is balanced, else −1.
- 2Recurse left; if −1, short-circuit −1 upward. Same for right.
- 3If |leftHeight − rightHeight| > 1, return −1.
- 4Otherwise return 1 + max(left, right). Root check ≠ −1 is the answer.
Key insight
Fusing the two queries (height + balanced) into one return value turns O(n²) into O(n) — a pattern that recurs across tree problems.
The solution
Watch out for
- Balance must hold at EVERY node, not just the root.
- Short-circuiting on −1 avoids wasted traversal of the sibling subtree.