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.
Binary Tree Maximum Path Sum
Core idea: A single post-order DFS returns the best downward gain a node can hand up to its parent —
node.val + max(0, leftGain, rightGain), where you clamp negative gains to 0 because a subtree that hurts is simply left out. But at each node you also consider the path that bends through it, using both children —node.val + max(0, left) + max(0, right)— and fold that into a running global maximum. Return one branch up; answer with both at the bend.
Problem, rephrased
You are tuning a power grid laid out as a binary tree. Every node is a substation with a signed value: a positive value is energy it contributes, a negative value is loss it imposes. A path is any sequence of substations connected edge-to-edge that bends at most once (it can go up one branch, through a node, and down another) — and it need not pass through the root. You want the single path whose total value is largest; you may even pick a path of just one substation if every connection only makes things worse.
Formally (LeetCode 124): given the root of a binary tree, a path is a sequence of nodes where each adjacent pair is connected by an edge, and each node appears at most once. The path does not need to pass through the root, and a path of a single node is allowed. Return the maximum sum of the node values along some path.
The trap: because values can be negative, the best path often excludes whole subtrees — attaching a losing branch only drags your total down.
| Input (tree, level-order) | Output | Why |
|---|---|---|
[1,2,3] |
6 |
The bend path 2 → 1 → 3 uses both children |
[-10,9,20,null,null,15,7] |
42 |
15 → 20 → 7; the root -10 and 9 are dropped |
[-3] |
-3 |
A single node is a valid path |
[2,-1] |
2 |
Attaching -1 would only lower the total, so drop it |
[-2,-1] |
-1 |
All negative — pick the least bad single node |
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