Recursion Tree

What Is a Recursion Tree?

A recursion tree is a visual representation of how recursive calls unfold. Each node represents one call to the function. The children of a node are the recursive calls made by that call.

Recursion tree for factorial(4):

factorial(4)
    └── factorial(3)
            └── factorial(2)
                    └── factorial(1)
                            └── factorial(0) = 1  ← base case

Shape: a single path — linear recursion makes one call per node.
Height: n  (4 levels deep for factorial(4))
Nodes:  n+1  (5 nodes for factorial(4))

Recursion tree for fib(4):

fib(4)
├── fib(3)
│   ├── fib(2)
│   │   ├── fib(1) = 1
│   │   └── fib(0) = 0
│   └── fib(1) = 1
└── fib(2)
    ├── fib(1) = 1
    └── fib(0) = 0

Shape: branching tree — binary recursion makes two calls per node.
Height: n  (4 levels for fib(4))
Nodes:  9  (count every node including base cases)

How to Draw a Recursion Tree

Four steps to draw any recursion tree:

Step 1: Write the initial call as the ROOT node.
  Label it with the function's arguments.

Step 2: For each non-base-case node, draw CHILDREN
  representing each recursive call it makes.
  Label each child with the arguments passed to it.

Step 3: Mark BASE CASE nodes — they have no children.
  Write their return value next to them.

Step 4: Label each node with the WORK it does
  EXCLUDING the recursive calls (the overhead per node).
  For merge sort: merge cost O(k) for a node of size k.
  For Fibonacci:  O(1) per node (one addition).

Tree 1: Linear Recursion — Factorial

factorial(4):

Level 0:  factorial(4)          work: O(1) — one multiply
Level 1:    factorial(3)        work: O(1)
Level 2:      factorial(2)      work: O(1)
Level 3:        factorial(1)    work: O(1)
Level 4:          factorial(0)  work: O(1) — base case

Height:      4 = n
Total nodes: 5 = n+1
Work/level:  O(1)
Total work:  O(1) × (n+1) levels = O(n)
Space:       O(n) — height of tree = max simultaneous frames

Tree 2: Binary Recursion — Fibonacci

Output:
fib(4)
  fib(3)
    fib(2)
      fib(1)
        = 1 [leaf]
      fib(0)
        = 0 [leaf]
    fib(2) = 1+0 = 1
  fib(3) = 1+1 = 2

  No wait — continuing:
  fib(4) calls fib(3) first (fully runs), then fib(2):

fib(4)
  fib(3)
    fib(2)
      fib(1)  = 1 [leaf]
      fib(0)  = 0 [leaf]
    fib(2) = 1+0 = 1
    fib(1)  = 1 [leaf]
  fib(3) = 1+1 = 2
  fib(2)
    fib(1)  = 1 [leaf]
    fib(0)  = 0 [leaf]
  fib(2) = 1+0 = 1
fib(4) = 2+1 = 3
Answer: 3

Counting Nodes in the Fibonacci Tree

fib(4) tree — all 9 nodes:

              fib(4)          level 0: 1 node
            /        \
        fib(3)       fib(2)  level 1: 2 nodes
        /    \       /    \
    fib(2) fib(1) fib(1) fib(0) level 2: 4 nodes
    /   \
fib(1) fib(0)                   level 3: 2 nodes (left branch only)

Total: 1+2+4+2 = 9 nodes ✓

Not a perfect binary tree! fib(n-2) subtree is shorter than fib(n-1).
For a full analysis: node count grows as ~φⁿ where φ ≈ 1.618 (golden ratio).
Approximated as O(2ⁿ) for simplicity.

Height of tree: 4 = n   (deepest path: fib(4)→fib(3)→fib(2)→fib(1))
Space complexity: O(n)  (height determines max simultaneous frames)

Tree 3: Divide and Conquer — Merge Sort

Merge sort's recursion tree is the canonical example for O(n log n) analysis.

mergeSort([8 elements]):

Level 0:  [8 elements]                              merge work: O(8)
          /                  \
Level 1:  [4 elements]      [4 elements]             merge work: O(4)+O(4) = O(8)
          /        \         /         \
Level 2:  [2]     [2]      [2]        [2]            merge work: 4×O(2) = O(8)
         / \     / \      / \        / \
Level 3: [1][1] [1][1]  [1][1]    [1][1]   base cases: no merge work

TOTAL WORK per level: O(n) = O(8)
NUMBER OF LEVELS:     log₂(n) = log₂(8) = 3

Total time: O(n) × log₂(n) levels = O(n log n)

Key insight:
  At every level, the total size of all subarrays = n.
  Merging all subarrays at a level costs O(n).
  There are log₂(n) levels.
  Therefore: O(n log n).

Output (n=4 for brevity):
mergeSort(0,3) — size 4
  mergeSort(0,1) — size 2
    mergeSort(0,0) — size 1
      [base case]
    mergeSort(1,1) — size 1
      [base case]
    merge(0..0, 1..1) — O(2) work
  mergeSort(2,3) — size 2
    mergeSort(2,2) — size 1
      [base case]
    mergeSort(3,3) — size 1
      [base case]
    merge(2..2, 3..3) — O(2) work
  merge(0..1, 2..3) — O(4) work
Sorted: [1, 2, 4, 7]

Tree 4: Unequal Branching — Binary Search

Binary search makes ONE recursive call, and its argument halves each time:

binarySearch(arr, target, 0, 15):  n=16

Level 0: search(0, 15)   — compare arr[7] with target
Level 1: search(0, 6)    OR  search(8, 15)   (only one branch taken)
Level 2: search(0, 2)    OR  search(3, 6)    etc.
Level 3: search(0, 0)    OR  ...
Level 4: lo > hi → return -1

Height:    log₂(16) = 4
Nodes:     at most log₂(n) + 1 = 5  (one per level, single branch)
Work/node: O(1)
Total:     O(log n)
Space:     O(log n) — max simultaneous frames = height

Tree shape: a single path (same as linear recursion, but depth is log n not n)

              search(0,15)
                   |
            search(8,15)     ← right half chosen
                   |
            search(8,11)
                   |
            search(8,9)
                   |
            search(9,9) → found or not found

Deriving Complexity from the Tree

Three-step method to derive time complexity from a recursion tree:

Step 1: IDENTIFY the work done at each node
  (excluding recursive calls — the "overhead" only)
  Merge sort node of size k: O(k)   (the merge step)
  Fibonacci node:            O(1)   (one addition)
  Binary search node:        O(1)   (one comparison)

Step 2: SUM the work at each LEVEL
  Level j of merge sort: 2^j nodes, each of size n/2^j
    Level 0: 1 node × O(n)     = O(n)
    Level 1: 2 nodes × O(n/2)  = O(n)
    Level 2: 4 nodes × O(n/4)  = O(n)
    Level j: 2^j × O(n/2^j)    = O(n)
  ↑ Every level has O(n) total work — the key insight for O(n log n).

Step 3: MULTIPLY by the NUMBER OF LEVELS
  Number of levels = height of tree
  Merge sort: log₂(n) + 1 levels × O(n) per level = O(n log n)
  Fibonacci:  height n × branching ~2 → O(2ⁿ) total nodes, O(1) each = O(2ⁿ)
  Binary search: log₂(n) levels × O(1) per level = O(log n)

Work-per-Level Analysis Table

Algorithm    Levels     Nodes/level   Work/node   Total/level   TOTAL
─────────────────────────────────────────────────────────────────────
Factorial    n          1             O(1)         O(1)          O(n)
Binary search log n     1             O(1)         O(1)          O(log n)
Merge sort   log n      2^j at level j O(n/2^j)   O(n)          O(n log n)
Fibonacci    n          up to 2^j     O(1)         O(2^j)        O(2^n)
Tower of Hanoi n        1 (path+branch) O(1)       O(1)          O(2^n)

Tree 5: Repeated Subproblems — Fibonacci Memoisation

The recursion tree reveals why naïve Fibonacci is exponential and why memoisation reduces it to linear:

fib(5) tree WITHOUT memoisation (25 total calls):

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) ← computed here
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2) ← computed AGAIN (same as above!)
│       ├── fib(1)
│       └── fib(0)
└── fib(3) ← computed AGAIN
    ├── fib(2) ← computed AGAIN
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

REDUNDANT WORK:
  fib(3) computed 2 times
  fib(2) computed 3 times
  fib(1) computed 5 times
  fib(0) computed 3 times
  Total calls: O(2ⁿ)

fib(5) tree WITH memoisation (linear calls):

fib(5) → fib(4) → fib(3) → fib(2) → fib(1) = 1
                                    → fib(0) = 0
                          ← uses cached fib(1) = 1
                ← uses cached fib(2) = 1
              ← uses cached fib(3) = 2
Total unique calls: n+1 = 6
Time: O(n), Space: O(n)

Output:
fib(20): naive=21891 calls, memo=21 calls
Naive fib(20) calls: 21891
Memo fib(20) calls:  21

Space Complexity from the Tree

Space complexity = maximum number of SIMULTANEOUS stack frames
                 = HEIGHT of the recursion tree

At any moment, only the frames on the current PATH from root
to the deepest active call are on the stack.
(Not all nodes — only the current root-to-leaf path.)

EXAMPLES:

Factorial(n):
  Tree height: n  →  Space: O(n)

Binary search:
  Tree height: log₂(n)  →  Space: O(log n)

Merge sort:
  Tree height: log₂(n)  →  Space: O(log n) for call stack
  (Plus O(n) for the auxiliary merge array — dominant term)

Fibonacci (naïve):
  Tree height: n  →  Space: O(n)
  (Even though the tree has O(2ⁿ) nodes, at any moment
   only the left-most path is on the stack — O(n) frames)

VISUALISATION:
  For fib(4), the call stack at deepest point:

  fib(4) [waiting for fib(3)]
    fib(3) [waiting for fib(2)]
      fib(2) [waiting for fib(1)]
        fib(1) [base case — returns immediately]

  Only 4 frames at once — not 9 (the total node count).
  Space = height = 4 = O(n), not O(2ⁿ).

Drawing Tool: Recursion Tree for Any Problem

TEMPLATE:

For a recursion of the form: T(n) = a·T(n/b) + f(n)
  a = number of recursive calls
  b = factor by which input shrinks
  f(n) = work done at each node (excluding sub-calls)

TREE STRUCTURE:
  Level 0: 1 node of size n         work: f(n)
  Level 1: a nodes of size n/b      work: a·f(n/b)
  Level 2: a² nodes of size n/b²    work: a²·f(n/b²)
  Level k: aᵏ nodes of size n/bᵏ   work: aᵏ·f(n/bᵏ)
  ...
  Level log_b(n): base cases

Number of levels: log_b(n)
Total nodes:      1 + a + a² + ... + a^(log_b n) = (a^(log_b n + 1) - 1)/(a-1)
                = O(n^(log_b a))

COMMON PATTERNS:
  T(n) = 2T(n/2) + O(n)   → merge sort:   O(n log n)
  T(n) = 2T(n/2) + O(1)   → binary tree:  O(n)
  T(n) = T(n/2) + O(1)    → binary search: O(log n)
  T(n) = 2T(n-1) + O(1)   → Tower of Hanoi: O(2ⁿ)
  T(n) = T(n-1) + O(n)    → selection sort (recursive): O(n²)

Common Mistakes When Drawing Recursion Trees

Confusing total nodes with simultaneous frames. Total nodes in a recursion tree determines time complexity. Simultaneous frames (tree height / path from root to leaf) determines space complexity. Fibonacci has O(2ⁿ) total nodes but O(n) space — only the current path is on the stack.

Forgetting that one branch completes before another starts. In a tree with two recursive calls, the entire left subtree runs to completion before the right subtree begins. The tree shows all calls that WILL happen, not calls that happen simultaneously.

Missing the merge or combine cost. The work at each node is the overhead at that level, not counting the recursive calls. For merge sort, this is the merge cost O(k). Forgetting to add this work per node underestimates the total complexity.

Drawing a complete binary tree for Fibonacci. The Fibonacci tree is NOT a complete binary tree — the left branch (fib(n-1)) is always deeper than the right (fib(n-2)). Total nodes is O(2ⁿ) but the tree is left-heavy, not symmetric.

Interview Questions

Q: How do you derive O(n log n) for merge sort using the recursion tree?

The recursion tree for merge sort has log₂(n) levels. At level j, there are 2^j subarrays each of size n/2^j. The merge cost at each subarray of size k is O(k). Total work at level j = 2^j × O(n/2^j) = O(n). Since every level costs O(n) and there are log₂(n) levels, total time = O(n log n).

Q: Why is the space complexity of merge sort O(log n) for the call stack (not O(n))?

The call stack holds one frame per level of the currently active path from root to leaf. At any moment, only one path is active — the recursion processes left subtrees completely before starting right subtrees. The tree has log₂(n) levels, so the maximum call stack depth is log₂(n) frames. (The total O(n) auxiliary array for merging is separate from the call stack space.)

Q: What does memoisation do to the recursion tree?

Memoisation "prunes" the tree — once a subproblem is computed and cached, any future call to the same subproblem returns the cached value immediately instead of branching into a subtree. For Fibonacci, this converts the tree from O(2ⁿ) nodes (exponential) to O(n) nodes (linear) — each unique subproblem fib(0) through fib(n) is computed exactly once.

Summary

A recursion tree visualises every call a recursive function makes:

• ›Each node = one function call
• ›Each edge = one recursive call relationship (parent calls child)
• ›Leaves = base cases

Reading complexity from the tree:

• ›Time = sum of work across ALL nodes = work per level × number of levels
• ›Space = HEIGHT of the tree = length of the longest root-to-leaf path

Four canonical tree shapes:

Key insight — work per level:

• ›Merge sort: every level costs O(n) total → O(n log n)
• ›Fibonacci: every level doubles the work → O(2ⁿ) total
• ›Binary search: every level costs O(1) → O(log n)

Memoisation prunes duplicate subtrees from the tree — converts O(2ⁿ) Fibonacci to O(n) by caching each unique subproblem result.

In the next topic, you will explore Tail vs Head Recursion — how the position of the recursive call relative to other computation changes execution order, stack behaviour, and whether tail call optimisation can be applied.