From equation to picture
The previous guide taught us to read recursive code and write down its recurrence — an equation like T(n) = 2 T(n/2) + cn that says 'the cost on size n is the cost of the recursive calls plus the work this call does itself'. That equation is correct but mute: it does not announce its own answer. The recursion-tree method is the most intuitive way to make it speak. The idea is simple and visual: unfold the recurrence into the actual tree of calls it describes, label each node with the local work it does, and then add everything up. You are not inventing new mathematics here — you are just bookkeeping, carefully.
Here is the whole recipe in one breath. The root is the original call on size n; its children are the subproblems it spawns; their children are the sub-subproblems, and so on down to the base cases at the leaves. On each node write only the local cost — the f(n) part of the recurrence, the work that node does outside its recursive calls, never counting its descendants. Then group the nodes by level (all nodes at the same depth), find the total work on each level, and sum across levels. The grand total is T(n). The art is almost entirely in two questions: how much work sits on one level, and how many levels are there?
The merge-sort tree, level by level
Take the canonical divide-and-conquer recurrence T(n) = 2 T(n/2) + cn, the one merge sort produces. The root does cn work and has two children, each a problem of size n/2 doing c(n/2) work. Those four grandchildren each have size n/4 and do c(n/4) work — and the pattern is already clear. At depth k there are 2^k nodes, each of size n/2^k, each doing c·(n/2^k) work. Multiply count by per-node cost: the level total is 2^k · c·(n/2^k) = cn. Every single level does exactly cn work. That balance is the heart of the answer.
T(n) = 2 T(n/2) + c*n
depth nodes size each work each LEVEL TOTAL
0 1 n c*n c*n
1 2 n/2 c*n/2 c*n
2 4 n/4 c*n/4 c*n
... ... ... ... ...
log n n 1 c c*n
-------------
levels = log2(n) + 1, each c*n -> c*n*(log n + 1) = O(n log n)Now the second question: how many levels? Each step down divides the size by 2, so after k levels the size is n/2^k. The recursion stops when the size reaches the base case of 1, i.e. when n/2^k = 1, which means k = log2(n). Counting the root, that is log2(n) + 1 levels. With cn work on each of about log n levels, the total is cn · (log n + 1) = Theta(n log n). Notice how the picture explains the answer rather than just asserting it: the n comes from the work spread across each level, and the log n comes from the height of the tree — the number of times you can halve n before hitting 1.
When the levels are not balanced
Merge sort is the easy case because every level cost the same. The recursion tree earns its keep precisely when they do not. Consider T(n) = 2 T(n/2) + c (constant work per call instead of linear). Same branching, same height: 2^k nodes at depth k, but now each does only c work, so the level total is 2^k · c — it doubles every level instead of staying flat. The bottom level alone has about n nodes doing c each, contributing cn, and it dwarfs everything above it. Summing a doubling series, the total is dominated by that last level: Theta(n). The leaves win.
Now flip it: T(n) = 2 T(n/2) + c·n^2. Each level's total is 2^k · c·(n/2^k)^2 = c·n^2 / 2^k — it halves every level instead of doubling, a shrinking geometric series. The root alone does c·n^2, and everything below sums to at most another c·n^2 (a geometric series with ratio 1/2 sums to twice its first term). So the total is Theta(n^2): the root dominates, the leaves are negligible. Three recurrences, identical shape, three different stories — balanced (n log n), bottom-heavy (n), top-heavy (n^2) — and the tree shows you which at a glance, by whether the level totals stay flat, grow downward, or shrink downward.
Trees with uneven branches
The method does not need a clean halving. Take T(n) = T(n/3) + T(2n/3) + cn, which arises when a split is lopsided. The two children shrink at different rates, so the tree is unbalanced: the n/3 branch reaches a leaf after about log_3(n) levels, while the 2n/3 branch keeps going until about log_{3/2}(n) levels. Still, here is the saving grace — the work on each full level is at most cn, because the sizes of all nodes on one level always add up to n (every original unit of input is split among them, never duplicated). The level totals stay at cn until branches start bottoming out.
So the total is cn times the height, and the height is set by the slowest-shrinking branch: the longest path repeatedly multiplies by 2/3, reaching 1 after about log_{3/2}(n) levels. That makes the total Theta(n log n) again — the same answer as a balanced split, with a different constant hidden in the base of the log. This is the recursion tree doing what the master theorem cannot: the master theorem requires equal-sized subproblems (a copies of size n/b), and an uneven split like this falls outside its form. The tree handles it directly, and the Akra-Bazzi method of the last guide in this rung is the general machinery that automates exactly this kind of uneven sum.
A guess, not yet a proof
Here is the honest caveat that keeps the recursion tree humble. Drawing it usually involves a sleight of hand: we assume n is a perfect power of b (a power of 2, of 3, and so on) so the levels come out clean, we treat the per-level sum as if it were exact, and we wave at the geometric series rather than bounding it term by term. Those shortcuts are fine for finding the answer, but they are not a proof. Real recurrences have floors and ceilings — T(floor(n/2)) and T(ceil(n/2)) — and a tree drawn for tidy powers does not by itself certify the messy general case.
That is exactly why the recursion tree and the next guide's method are partners, not rivals. Use the tree to generate a confident guess — 'this looks like Theta(n log n)' — and then hand that guess to the substitution method, which uses guess-and-verify with induction to prove a clean bound that holds for all n, floors and ceilings included. A useful sanity check before you trust a tree-derived guess: if the level totals form a geometric series, the answer is whichever end dominates (the root, or the leaves times their count); if they are flat, multiply one level's cost by the number of levels. Get the qualitative shape from the tree; get the certificate from substitution.