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.
Lowest Common Ancestor of a Binary Tree II
Core idea: This is classic LCA with the safety net removed —
porqmight not be in the tree at all. So you can't just find the split point and trust it; you must also count that you genuinely saw both targets, and only then is the split point a real answer.
Problem, rephrased
You have the org chart of a company drawn as a binary tree: the CEO at the root, each employee with a manager (parent) and up to two direct reports (children). Someone hands you two name badges, p and q, and asks: "Who is the most junior manager with authority over both of these people?"
Here's the twist that makes this Binary Tree II and not the classic version: the two badges might belong to people who don't work here. Maybe q already quit, or the badge is from a different company entirely. The classic LCA problem guarantees both p and q live in the tree; this one does not. If either target is missing from the tree, the honest answer is "there is no such manager" → return None.
(The guaranteed-present version is covered in the Binary Tree topic. This lesson is purely about handling the not-guaranteed twist.)
This is a general binary tree — no BST ordering — so you must actually search the structure rather than navigate by value. You're given node references, so identity (node is p) is what matters.
Inputs / outputs
| Input | Meaning | Output |
|---|---|---|
root |
root of a binary tree | the LCA TreeNode of p and q, or None |
p, q |
two nodes that may or may not exist in the tree | None if either is absent |
The whole game is that last cell: return None unless both p and q were truly found.
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