Divide and Conquer on Trees
You'll learn how to break tree problems into smaller subtree problems and combine their solutions at each node.
The Core Idea
When you apply divide and conquer to tree problems, you solve the problem for each child subtree recursively, then use those results to compute the answer for the current node. The tree's natural recursive structure makes it perfect for this approach: every subtree is itself a valid tree.
Think of it like managing a company hierarchy. To calculate total sales for a division, each manager first asks their direct reports for their team's sales (solve for subtrees), then adds their own contribution and reports upward (combine at root).
How It Works
The pattern follows these steps:
- Base case: Handle leaf nodes or empty subtrees
- Recursive calls: Solve the problem for left and right children (or all children in general trees)
- Combine: Merge the subproblem solutions with information from the current node
For example, computing a tree's height:
- A null node has height 0 (base case)
- For any node, get heights of left and right subtrees (divide)
- Return 1 + max(left_height, right_height) (conquer/combine)
This strategy works for many tree problems: computing diameter, checking if balanced, finding maximum path sums, counting nodes, and more. Each problem defines its own "combine" logic, but the divide-and-conquer structure remains consistent.
The recursion naturally traverses the entire tree, touching each node once, typically giving O(n) time complexity where n is the number of nodes.
Key Takeaway: Divide and conquer on trees means recursively solving for subtrees first, then combining their answers at each parent node—leveraging the tree's inherent recursive structure.