Recursion Tree Method Interview Questions: Worked Traces and Model Answers
Learn how to turn a recurrence into a recursion tree, total each level, include the leaves and state a tight bound. Worked examples cover exact traces, dominant regions, code analysis and interview follow-ups.
KnowledgeGate Team
Exam prep & CS education

Candidates often draw the right branches but report one node's work as the cost of an entire level. Others use the branching factor to calculate tree height or stop before charging the leaves. A reliable interview answer names the branching factor, shrink factor, per-node work, level totals, leaf cost and tight bound, then tests them on exact n=8 and uneven-split examples.
What is the recursion tree method? Give the 30-second model answer
A recursion tree is an accounting method for a recurrence. It is not the program's live call stack. For T(n)=aT(n/b)+f(n), with T(1)=c and n a power of b, level i contains a^i nodes. Each node handles an input of size n/b^i, so that level costs a^i f(n/b^i).
The height is h=log_b n, and the number of leaves is a^h=n^(log_b a). Therefore, the full cost is
sum from i=0 to h-1 of a^i f(n/b^i) + c a^h.
A strong answer identifies which levels dominate, explains why, and then states a tight Theta bound. If the notation needs revision, remember from the time-complexity and asymptotic-notation guide that Big-O is an upper bound, while the worked trees below justify tight Theta results.
Solve T(n)=2T(n/2)+n at n=8 without skipping a level
Set the cost model first: T(1)=1, every non-base call contributes exactly its current input size, and n=8. A substitution check gives:
T(2)=2T(1)+2=2(1)+2=4T(4)=2T(2)+4=2(4)+4=12T(8)=2T(4)+8=2(12)+8=32
Now check the same answer through the tree.
Level | Nodes | Size per node | Work per node | Level total |
|---|---|---|---|---|
0 | 1 | 8 | 8 | 8 |
1 | 2 | 4 | 4 | 8 |
2 | 4 | 2 | 2 | 8 |
3 | 8 | 1 | Base cost 1 | 8 |
The exact sum is 8+8+8+8=32, matching substitution. In general, there are log_2 n non-leaf levels, each costing n, followed by n leaves of constant cost 1. Thus
T(n)=n log_2 n+n=Theta(n log n).
The number 32 is the exact result under this cost model. Theta(n log n) describes how the cost grows.

How do you tell whether the root, every level or the leaves dominate?
Compare three exact trees with n=8 and T(1)=1.
Recurrence | Level totals, including leaves | Exact total | Tight bound |
|---|---|---|---|
|
| 120 |
|
|
| 32 |
|
|
| 65 |
|
The reason is algebraic, not just visual. When f(n)=n^d, non-leaf level i costs n^d(a/b^d)^i. The ratio r=a/b^d is 1/2 in the first tree, 1 in the second and 3/2 in the third. Costs therefore shrink toward the leaves, remain tied, or grow toward the leaves.
Always include the leaf term. In the third tree, non-leaf work is 8+12+18=38, but the 27 base-case leaves make the exact total 38+27=65. Those exact totals depend on the stated unit-cost model. They are not substitutes for the asymptotic results.
Derive the recurrence from code before drawing the tree
Start from the operations, not from the shape you expect to see.
analyse(n):
if n == 1: return 1
total = 0
repeat 3 times:
total = total + analyse(n/2)
for i = 1 to n:
total = total + 1
return totalThere are three recursive calls, so a=3. Each receives n/2, so b=2. The linear loop contributes f(n)=Theta(n). Under the exact unit-cost model used above, the recurrence is T(n)=3T(n/2)+n. It gives T(8)=65 and T(n)=Theta(n^(log_2 3)).
Two traps matter here. Three sequential calls change the number of children, not the shrink factor. Receiving n/2 does not make a=2. For more practice explaining recursion, data structures and complexity together, DSA using Java is an optional learning route.
Which recursion-tree mistakes make a correct-looking answer wrong?
First, per-node work is not level work. At level 1 of 3T(n/2)+n for n=8, each of three nodes costs 4, so the level costs 3 x 4=12, not 4.
Second, height comes from shrinkage. 3T(n/2) still has log_2 n levels, so n=8 has 3 edges from root to leaf, not log_3 8.
Third, leaves carry cost. The binary tree above has 8 leaves, changing an incomplete 8+8+8=24 into the exact 32.
Fourth, a tight result needs the sum. Writing only O(n log n) after finding equal levels discards the justified lower bound. State Theta(n log n).
Use this repair checklist: label nodes, size, per-node cost, level total, height and leaves, then sum.
What follow-ups expose whether you understand the tree?
Here are four answers worth rehearsing aloud.
How many calls occur for
n=8? The full binary tree contains1+2+4+8=15call nodes.Is auxiliary space also 15? No. With sequential calls and constant local state, the deepest active chain is
8 -> 4 -> 2 -> 1, which means 4 frames or 3 edges. Stack space isO(log n).Can the tree prove the exact value 32? Yes, only because
T(1)=1,n=8and the exact unit work were stated.Does the log base change Theta? A constant base change multiplies the logarithm by a constant, so it does not.
After these recursion-tree follow-ups, the broader DSA interview-question patterns provide a wider drill. The Coding & DSA category is another route for structured learning.
Can a recursion tree help when the Master Theorem does not apply?
Yes. Consider T(n)=T(n-1)+n, with T(1)=1. Its recursive size is n-1, not n/b for a constant b>1, but expansion still exposes the sum. At n=5, the chain costs are 5, 4, 3, 2, 1, so T(5)=15. Generally,
1+2+...+n=n(n+1)/2=Theta(n^2).
Now consider T(n)=T(n/3)+T(2n/3)+n. At n=9, the root costs 9. Level 1 has sizes 3 and 6, totalling 9. Level 2 has sizes 1, 2, 2, 4, again totalling 9. Standard floor and ceiling conventions handle non-integral later splits. Shallow complete levels conserve total size, while path depths remain between constant multiples of log n, supporting Theta(n log n). A formal proof can use Akra-Bazzi.
An equal-subproblem recurrence fits the Master Theorem; the Master Theorem for GATE post owns its case tests and logarithmic boundary comparison. This post focuses on tree accounting when the split is uneven or decreases by one, where expansion makes each level and leaf charge visible.
Recursion tree interview answer: the 45-second version and next step
Use six spoken steps: write the recurrence; label the number and size of children; compute one node's non-recursive work; multiply for each level total; find height and leaf cost; sum, identify the dominant region and state a tight Theta bound. For 2T(n/2)+n, every non-leaf level costs n, there are log_2 n such levels, and the leaves add n, giving Theta(n log n).
Rehearse the core, leaf-dominant and n-1 examples aloud. The Interview & Resume Preparation Course is an optional structured route for practising clear spoken answers.
Keep learning
Recursion Tree Method MCQs: 12 Solved Questions with Explanations
Solve 12 recursion tree MCQs covering exponential trees, uneven splits, harmonic level sums, square-root arguments, and exact recurrence forms.
Recursion in C: Stack Frames, a Hand-Tracing Method and Solved GATE Questions
Trace recursive C programs without guessing. Follow factorial returns, prints on descent and unwind, Fibonacci call counts, and maximum stack depth.
Basic Recursion in C: Call Stack, Worked Traces and Exam Patterns
Learn how recursive C functions descend, stop and unwind. Trace factorial and printed output, count Fibonacci calls, and compare recursion with iteration.
Recursion with Pointers in C: Concepts, Traces and Worked Examples
Learn how local pointer copies interact with shared array memory, then trace one mutating sum and one reverse-print function from descent to unwind.





