Divide and Conquer on Trees
What is this?
Lots of hard-looking tree questions melt away with one habit: solve the small pieces first, then combine. You visit the deepest nodes, get an answer for each little branch, and let those answers bubble back up to their parent — the way you'd add up the cost of every room to get the cost of a whole house. Each spot in the tree returns one number upward while quietly keeping score of the best answer seen so far.
💡 Fun fact: This bottom-up combining is a baby version of dynamic programming — you compute each subproblem exactly once, so even a giant tree is solved in a single sweep.
🔓 The 6 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: A huge family of tree problems is solved by one move: a post-order DFS where each call returns a single value to its parent, while updating a shared (global/nonlocal) answer that may combine both children. The return value is what a parent can extend; the answer is what bends at the current node. Spotting which information flows up (returned) versus down (passed as arguments) is the whole skill.
The pattern
The recurring tension: a parent can only continue one branch through a child, but the optimal answer often uses both branches meeting at a node. So you return one, but score with both.
The problems
- Diameter, Max Path Sum, Longest Univalue Path — the canonical trio: return an arm/height/gain upward, update the answer with
left + right. - Smallest Subtree with all the Deepest Nodes — return a richer tuple
(depth, covering-node); equal child depths mean this node is the answer. - LCA II — fuse an existence check into the search with a found-counter, trusting the result only if both targets were truly seen.
- Maximum Difference Between Node and Ancestor — the mirror image: information flows down (carry the path min/max as arguments).
Key takeaways
- Post-order DFS: return one thing, update another — the engine behind diameter, path sum, and more.
- Return one branch upward; the answer may bend using both branches at a node.
- Richer return types (tuples, counters) collapse multi-pass solutions into one O(n) pass.
- Direction matters: bottom-up returns info; top-down carries info down as arguments.
- Why interviewers love it: it tests whether you can design what each recursive call communicates.
Order: Diameter → Maximum Path Sum → Longest Univalue Path → LCA II → Smallest Subtree of Deepest Nodes → Max Difference Node–Ancestor.
Diameter of Binary Tree
Core idea: The longest path in a tree bends at exactly one node — its highest point. At that bend, the path is
leftHeight + rightHeightedges. So make one post-order pass where each call returns its subtree's height to its parent, and as a side effect updates a running best withleftHeight + rightHeight. One traversal computes the answer for every possible bend point —O(n)total instead of recomputing heights from scratch at every node.
Problem, rephrased
Forget the textbook phrasing. Here's the scenario:
You manage a small office network wired as a tree — every machine connects to others by cables, with no loops, so there's exactly one route between any two machines. You want the worst-case hop count: across all pairs of machines, what's the largest number of cables on the route between them? That longest route is the network's diameter, and it tells you the maximum communication latency the topology can ever impose.
In tree terms: given the root of a binary tree, the diameter is the length in edges of the longest path between any two nodes. That path may run between two leaves, between a leaf and an internal node — and it need not pass through the root.
Tree (root ...) |
Longest path | Diameter (edges) |
|---|---|---|
[1,2,3,4,5] |
4 → 2 → 1 → 3 (or 5→2→1→3) |
3 |
[1] (single node) |
the node alone | 0 |
[] (empty) |
nothing | 0 |
1→2→3→4 (right-skewed chain) |
the whole chain | 3 |
The key trap: the diameter is measured in edges, not nodes, and the deepest two leaves might both hang off some internal node, so the longest path can completely miss the root.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson