Recursion Tree Method

Recursion Tree Method

When you write a recursive algorithm, its running time obeys a recurrence — a formula that defines the cost on an input of size n in terms of the cost on smaller inputs, plus whatever work the current call does itself. The recursion tree method is the most visual way to solve such a recurrence: you literally draw the tree of recursive calls, tag every node with the work it does (not counting its children), then add everything up. The genius of the technique is that it turns an intimidating self-referential equation into simple arithmetic — count the work per level, count the levels, and sum.

Think of it as unrolling the recursion by hand. The root is the original call. Its children are the sub-calls it spawns. Their children are the sub-sub-calls, and so on, until you hit the base case. The total time is nothing more than the sum of the work written on every node.

Precise definition

Given a recurrence T(n) = a·T(n/b) + f(n) (with a sub-calls each on inputs a factor b smaller, and f(n) non-recursive work), the recursion tree is built as follows:

• Root is labelled with f(n) — the work the top call does outside its recursive calls.
• The root has a children, each a subproblem of size n/b, so each is labelled f(n/b).
• Continue expanding until subproblem size reaches the base case (size 1), which occurs at depth roughly logbn.

Then compute two quantities: the work at each level (number of nodes on the level × work per node) and the number of levels. T(n) is the sum of level-costs over all levels, including the bottom row of leaves (the base cases). The tree method is not a shortcut that hides the algebra — it is the algebra, drawn.

Worked example — merge sort: T(n) = 2T(n/2) + cn

Merge sort splits an array in two, sorts each half, and merges in linear time. So a = 2, b = 2, f(n) = cn. Let us count with concrete numbers: n = 8 and c = 1.

• Level 0: 1 node of size 8 → work = 8.
• Level 1: 2 nodes of size 4 → 2 × 4 = 8.
• Level 2: 4 nodes of size 2 → 4 × 2 = 8.
• Level 3: 8 leaves of size 1 → 8 × 1 = 8.

Every level costs exactly cn = 8 — because doubling the node count exactly cancels the halving of node size. The number of levels is log28 + 1 = 4. Total work = 8 × 4 = 32. In general T(n) = cn·(log2n + 1) = Θ(n log n). That is merge sort's running time in best, worst, and average case — the tree is identical regardless of input, which is exactly why merge sort has no bad cases.

The key insight: sum the level-costs as a geometric series

Not every tree has equal levels. Compare the level totals as you go down — they form a geometric series, and its ratio decides everything:

• Balanced (equal per level) — e.g. merge sort. Each of log n levels costs the same, giving Θ(f(n)·log n).
• Root-heavy (decreasing) — e.g. T(n) = 2T(n/2) + n2. Level i costs 2i·(n/2i)2 = n2/2i, halving each level. The series is dominated by the root: Θ(n2).
• Leaf-heavy (increasing) — e.g. T(n) = 4T(n/2) + n. Work grows down the tree, so the Θ(nlogba) leaves dominate: Θ(n2).

This is exactly the intuition behind the Master Theorem — its three cases are just "decreasing / equal / increasing series." The tree method is the honest derivation; the Master Theorem is the memorised shortcut.

Pitfalls and what an interviewer probes

• Forgetting the leaves. The bottom row is real work. In leaf-heavy trees it is the dominant term — counting only internal nodes gives the wrong answer.
• Miscounting the depth. Size-n/bi reaches 1 at i = logbn. For subtract-and-recur like T(n)=T(n-1)+c the depth is n, not log n — a classic trap that turns O(n) into a mistaken O(log n).
• Node count vs. work per node. A level's cost is count × per-node work; conflating the two is the most common arithmetic slip.
• Treating it as proof. The tree gives you a guess; a rigorous answer uses the substitution method to verify the bound by induction. Interviewers love asking "how would you prove that?"
• Unbalanced splits. T(n)=T(n/3)+T(2n/3)+cn gives a lopsided tree — longest path log3/2n — yet still sums to Θ(n log n). Being able to reason about ragged trees signals real fluency.

When it matters in practice, and trade-offs

Reach for the recursion tree when the recurrence has an unusual f(n) (like n log n or n/log n) that the Master Theorem's clean cases do not cover, or when a split is uneven. It also builds the intuition that later lets you apply the Master Theorem instantly. Compared to neighbours: the Master Theorem is faster but only handles the aT(n/b)+f(n) shape with well-behaved f; the substitution method proves a bound rigorously but needs you to guess it first — the tree is the ideal guess-generator; Akra–Bazzi generalises to arbitrary unequal splits but is heavier machinery. Its one weakness: for messy or non-polynomial f(n), summing the series exactly can itself be hard, so the tree gives the shape of the answer while careful algebra nails the constant.

Key takeaways

• Draw the call tree, label each node with its own work f(size), then T(n) = sum over all levels including the leaf row.
• Level cost = (number of nodes) × (work per node); the sequence of level costs is a geometric series whose ratio (decreasing / equal / increasing) picks the dominant term — root, all-levels, or leaves.
• Merge sort's tree has log2n + 1 levels each costing cn, so Θ(n log n) in best, worst, and average case.
• Use the tree to guess the bound, the Master Theorem to shortcut the standard shape, and substitution to prove it — and always double-check depth and the leaf count.