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.