Course contentsShow
← Computer Science
Lesson 853 of 2,87220. Recursion Patterns and TechniquesFree lesson

Divide and Conquer on Trees

Applying divide and conquer to tree problems: solve for subtrees and combine at root.

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:

  1. Base case: Handle leaf nodes or empty subtrees
  2. Recursive calls: Solve the problem for left and right children (or all children in general trees)
  3. 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.