What the Recursion Tree Method Is
A recursive algorithm does not do all its work in one place. It does a little at the top, hands the rest to smaller copies of itself, and those copies do the same. The recursion tree method makes that structure visible: draw the calls as a tree, work out what each level costs, and add the levels up.
Of the three standard techniques it is the only one that both derives an answer and explains it. The Master Theorem gives you a result with no insight into where it came from. The substitution method proves a result you must already have guessed. The recursion tree shows you where the time actually goes — and it works on recurrences the other two cannot express.
Anatomy of a Recursion Tree
- A node holds the non-recursive cost of one call.
- Not the total cost of that call — only the f(n) part. The recursive work is represented by the node's children.
- A node's children are the subproblems it spawns.
- T(n) = 2T(n/2) + n gives every node two children, each labelled with half its parent's size.
- A level's cost is the sum across that row.
- This is the quantity the method is built around: how much the whole recursion spends at depth i.
- The depth is how many times you can shrink n before hitting the base case.
- Dividing by b gives depth log_b n. Subtracting a constant gives depth n — a much taller tree.
- The leaves are the base cases.
- For a-way branching over depth log_b n there are a^(log_b n) = n^(log_b a) of them, and each costs Θ(1).
The single most important rule: a node holds f(n), not T(n). The node is the work one call does by itself; everything the call delegates is represented by the nodes hanging beneath it. Labelling a node T(n) counts the whole subtree twice.
Worked Example 1 — T(n) = 2T(n/2) + n
The merge sort recurrence. Each call does n units of work merging, then hands two half-size problems to its children:
| Level i | Nodes | Cost of each | Level total |
|---|---|---|---|
| 0 | 1 | n | 1 × n = n |
| 1 | 2 | n/2 | 2 × n/2 = n |
| 2 | 4 | n/4 | 4 × n/4 = n |
| i | 2ⁱ | n/2ⁱ | 2ⁱ × n/2ⁱ = n |
| log₂n | n | 1 | n × Θ(1) = Θ(n) |
Every level costs n. The size reaches 1 after log₂n halvings, so there are log₂n levels above the leaves, and the leaf row contributes Θ(n):
T(n) = n + n + n + … + nlog₂n levels = n · log₂n + Θ(n)levels plus leaves = Θ(n log n)The tree also explains why the answer has that shape, which the Master Theorem never does. The n log n is a product of two independent facts: each level costs n because doubling and halving cancel, and there are log n levels because halving reaches 1 that fast.
Worked Example 2 — When the Levels Shrink
Solve T(n) = 3T(n/4) + n². Now the node count triples while each subproblem's cost drops by a factor of 16, so the levels do not balance:
| Level i | Nodes | Cost of each | Level total |
|---|---|---|---|
| 0 | 1 | n² | n² |
| 1 | 3 | (n/4)² = n²/16 | 3n²/16 |
| 2 | 9 | (n/16)² = n²/256 | 9n²/256 |
| i | 3ⁱ | n²/16ⁱ | (3/16)ⁱ · n² |
Each level costs 3/16 of the one above it. That is a decreasing geometric series, and a geometric series is dominated by its first term — so instead of multiplying by the depth, sum the series:
T(n) ≤ n² · Σ (3/16)ⁱi from 0 to ∞ = n² · 1 / (1 − 3/16)geometric sum = (16/13) · n² = Θ(n²)the root dominatesThe leaves are negligible here: there are 3^(log₄n) = n^(log₄3) ≈ n^0.79 of them, far fewer than the n² work done at the root. Computing the ratio T(n)/n² numerically converges to 1.2308, which is 16/13 exactly — the constant the series predicts.
The Three Shapes a Tree Can Take
Every recursion tree falls into one of three patterns, and identifying which one you have is the whole method:
| Shape | Level costs | What dominates | Total | Master Theorem |
|---|---|---|---|---|
| Decreasing | Each level costs less than the one above | The root dominates; the series converges | Θ(f(n)) | Case 3 |
| Constant | Every level costs the same | Cost = one level × the depth | Θ(f(n) · log n) | Case 2 |
| Increasing | Each level costs more than the one above | The leaves dominate the sum | Θ(n^(log_b a)) | Case 1 |
The last column is not a coincidence. The Master Theorem is this table, proved once in general. Its three cases are these three shapes, and its watershed function n^(log_b a) is just the leaf count. Understanding the tree means the theorem stops being three rules to memorise and becomes one idea with three outcomes.
Worked Example 3 — Unequal Subproblems
Solve T(n) = T(n/3) + T(2n/3) + n. There is no single b here, so the Master Theorem cannot even state this recurrence. The tree handles it without complaint:
The children of any node have sizes summing to its own, so every complete level still costs exactly n. What changes is the depth, which is now different depending on which branch you follow:
- The shortest path divides by 3 each step.
- It reaches the base case after log₃n levels.
- The longest path multiplies by 2/3 each step.
- It survives for log_{3/2}n levels — the height of the tree.
Above the shortest leaf, every level costs exactly n; below it, levels cost at most n. That brackets the total between n·log₃n and n·log_{3/2}n. Both are Θ(n log n) — the bases differ only by a constant factor — so T(n) = Θ(n log n).
This is the practical case that matters most: it is the recurrence for quick sort with a consistently lopsided pivot. Even a split as bad as 1-to-2 at every single step still gives n log n. Quick sort only degrades to n² when the split is as extreme as 1-to-(n−1).
Worked Example 4 — Filling a Master Theorem Gap
Solve T(n) = 2T(n/2) + n/log n. The Master Theorem is silent here: the watershed is n, and n/log n is smaller than n but not polynomially smaller, so it falls between Cases 1 and 2. The tree simply computes it.
At depth i there are 2ⁱ nodes, each of size n/2ⁱ, so each costs (n/2ⁱ)/log(n/2ⁱ) = (n/2ⁱ)/(log n − i). Multiplying by the node count:
level i cost = 2ⁱ · (n/2ⁱ)/(log n − i) = n / (log n − i)the 2ⁱ cancelsT(n) = Σ n/(log n − i)i from 0 to log n − 1 = n · (1 + 1/2 + 1/3 + … + 1/log n)reindexed = n · H(log n)a harmonic sum = Θ(n log log n)since H(m) ≈ ln mThe harmonic series is what the Master Theorem's gap is hiding. Neither geometric nor constant, it sums to a logarithm — giving an answer, n log log n, that none of the three cases could have produced. Evaluating the recurrence numerically confirms it: T(n)/(n log log n) settles at about 0.72 and stays there as n grows.
A Method You Can Follow Every Time
- Draw the root and label it with f(n), not T(n).
- The node holds only the work done outside the recursive calls.
- Expand two or three levels until the pattern is obvious.
- You are looking for how the node count and the per-node size change from one row to the next.
- Write the cost of a general level i.
- Number of nodes at depth i, multiplied by the cost of one node at depth i.
- Find the depth of the tree.
- Solve for when the subproblem size reaches 1 — log_b n for division, n for subtraction.
- Sum the level costs, and add the leaves.
- Whether the sum is geometric, arithmetic or harmonic decides everything.
- Verify the result with the substitution method.
- The tree is an argument, not a proof. Induction is what makes it rigorous.
T(n) = Σ (cost of level i) + (cost of the leaves)How It Compares to the Other Two Methods
| Method | Works on | Effort | What you get |
|---|---|---|---|
| Recursion tree | Any recurrence | Draw and sum | The answer plus the intuition — but informally |
| Master Theorem | T(n) = aT(n/b) + f(n) only | Almost none | A rigorous Θ bound, instantly |
| Substitution | Any recurrence | Needs a guess up front | A rigorous proof of a bound you already have |
In practice the tree and substitution are used together: the tree finds the answer, and induction proves it. The Master Theorem is the shortcut you reach for first, and the tree is what you fall back on the moment the recurrence stops fitting its template.
Common Mistakes
- Putting T(n) in a node instead of f(n).
- A node's own cost is only the non-recursive work. Writing T(n) double-counts everything below it.
- Assuming every leaf sits at the same depth.
- That is only true for equal splits. In T(n) = T(n/3) + T(2n/3) + n one branch bottoms out far sooner than the other, and levels below that depth cost less than n.
- Treating the tree as a proof.
- A drawing with an "…" in it is an argument by pattern. Textbooks pair every tree with a substitution proof for exactly this reason.
- Getting the depth wrong for subtractive recurrences.
- T(n) = T(n − 1) + n has depth n, not log n. The tree is a single chain of n nodes.
- Summing a geometric series as though it were constant.
- If levels shrink by a constant ratio, the total is a constant multiple of the first level — do not multiply by the depth.
- Forgetting the leaves.
- In a bottom-heavy tree, the leaf row is the entire answer, and it is the one row the level formula usually does not cover.
Frequently Asked Questions
What is the recursion tree method?
It is a technique for solving a recurrence by drawing the recursion as a tree, where each node holds the non-recursive cost of one call and its children are the subproblems it creates. You compute what each level of the tree costs, work out how deep the tree goes, and add the levels up. The total is the solution to the recurrence.
Is a recursion tree a proof?
Not on its own. Drawing a few levels and extending the pattern with an ellipsis is an informal argument, not a rigorous one. Standard practice is to use the tree to find the answer and then confirm it with the substitution method, which supplies the induction the drawing lacks.
How do I find the depth of a recursion tree?
Ask how many times the input must shrink before it reaches the base case. If each level divides by b, the depth is log_b n. If each level subtracts a constant, the depth is proportional to n. Getting this wrong is the most common source of an incorrect answer, since the depth multiplies everything.
How many leaves does a recursion tree have?
If every node has a children and the depth is log_b n, the leaf count is a^(log_b n), which equals n^(log_b a). That expression is exactly the watershed function from the Master Theorem, because the two methods are measuring the same thing: the total cost sitting at the bottom of the tree.
When is a recursion tree better than the Master Theorem?
Whenever the Master Theorem does not apply — unequal subproblem sizes such as T(n/3) + T(2n/3), subtractive recurrences such as T(n − 1), or recurrences that fall into the theorem's gaps like T(n) = 2T(n/2) + n/log n. The tree handles all of these, because it makes no assumption about the shape of the recurrence.
What do the three tree shapes mean?
If level costs decrease geometrically, the root dominates and the answer is Θ(f(n)). If every level costs the same, the answer is that cost times the depth. If level costs increase, the leaves dominate and the answer is Θ(n^(log_b a)). Those three shapes are precisely the three cases of the Master Theorem, seen from the other side.
Key Takeaways
- Draw the calls as a tree, cost each level, and sum the levels plus the leaves.
- A node holds f(n) — the non-recursive work — never T(n).
- Level costs either shrink, stay equal or grow, and those three shapes are the Master Theorem's three cases.
- Depth is log_b n when the input is divided and n when it is decremented; the depth multiplies everything.
- A geometric series is dominated by its first term — sum it, do not multiply it by the depth.
- The tree gives you the answer and the intuition; use substitution to turn it into a proof.