---
title: "Recursion tree for Tower of Hanoi, 4 disks"
subject: "Data Structure and Algorithm"
chapter: 5
key: "semester_4/data_structure_and_algorithm:toh-recursion-tree-4-disks"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/toh-recursion-tree-4-disks
site: BCT Engineering
---

# Recursion tree for Tower of Hanoi, 4 disks

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2072 Asoj, 5 marks
- Video: [Easy Trick to Draw Tower of Hanoi Recursion Tree in Minutes (TOH)](https://www.youtube.com/watch?v=Wgh10kwb3cw) — Aayush Dhakal
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/toh-recursion-tree-4-disks
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

Draw recursion tree for Tower of Hanoi assuming 4 disks.

## Short answer

For 4 disks, the recursion tree has depth 4, 15 nodes (2^4-1). Each internal node executes a disk move between its children. The move sequence: 1 A→B, 2 A→C, 1 B→C, 3 A→B, 1 C→A, 2 C→B, 1 A→B, 4 A→C, 1 B→C, 2 B→A, 1 C→A, 3 B→C, 1 A→B, 2 A→C, 1 B→C.

## Answer

Using TOH(n, from, to, aux) with the call TOH(4, A, C, B), each call makes two calls for n-1 disks and moves disk n between them.

```text
TOH(4,A,C,B)                         [move 8: disk 4 A->C]
├─ TOH(3,A,B,C)                      [move 4: disk 3 A->B]
│  ├─ TOH(2,A,C,B)                   [move 2: disk 2 A->C]
│  │  ├─ TOH(1,A,B,C)                [1: disk 1 A->B]
│  │  └─ TOH(1,B,C,A)                [3: disk 1 B->C]
│  └─ TOH(2,C,B,A)                   [move 6: disk 2 C->B]
│     ├─ TOH(1,C,A,B)                [5: disk 1 C->A]
│     └─ TOH(1,A,B,C)                [7: disk 1 A->B]
└─ TOH(3,B,C,A)                      [move 12: disk 3 B->C]
   ├─ TOH(2,B,A,C)                   [move 10: disk 2 B->A]
   │  ├─ TOH(1,B,C,A)                [9: disk 1 B->C]
   │  └─ TOH(1,C,A,B)                [11: disk 1 C->A]
   └─ TOH(2,A,C,B)                   [move 14: disk 2 A->C]
      ├─ TOH(1,A,B,C)                [13: disk 1 A->B]
      └─ TOH(1,B,C,A)                [15: disk 1 B->C]
```
Structure: root, 2 children, 4 grandchildren, 8 leaves.

Facts about the tree (checked with a program):
- Levels: 4 (n = 4, 3, 2, 1), with 1, 2, 4, 8 nodes.
- Total calls = 2⁴ − 1 = 15, so there are 15 moves.
- Moves are made in in-order sequence: 1 to 15 as numbered above.
- Move sequence: 1:D1 A→B, 2:D2 A→C, 3:D1 B→C, 4:D3 A→B, 5:D1 C→A, 6:D2 C→B, 7:D1 A→B, 8:D4 A→C, 9:D1 B→C, 10:D2 B→A, 11:D1 C→A, 12:D3 B→C, 13:D1 A→B, 14:D2 A→C, 15:D1 B→C.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How many calls (nodes) does the TOH recursion tree for 4 disks have?
   A. 16
   B. 8
   C. 15
   D. 14
   Answer: C. 2^4 - 1 = 15 calls and 15 moves. (Key point: Total calls)

2. How many nodes are at each level from the root for 4 disks?
   A. 1, 2, 3, 4
   B. 1, 3, 7, 15
   C. 4, 3, 2, 1
   D. 1, 2, 4, 8
   Answer: D. Each call makes two calls, doubling the nodes per level; the 8 leaves are TOH(1,...). (Key point: Nodes per level)

3. Which move occurs at the root TOH(4,A,C,B)?
   A. Disk 4 from A to C as move 8
   B. Disk 1 from A to B as move 1
   C. Disk 4 from A to B as move 15
   D. Disk 3 from A to B as move 4
   Answer: A. The middle (in-order 8th) move is the largest disk A to C. (Key point: Root move)

4. What is the left child of TOH(4,A,C,B)?
   A. TOH(3,A,C,B)
   B. TOH(3,A,B,C)
   C. TOH(3,B,C,A)
   D. TOH(4,A,B,C)
   Answer: B. The first call moves n-1 disks from source to the auxiliary peg: TOH(n-1, from, aux, to). (Key point: First child call)

## Related in Data Structure and Algorithm

- [Tree recursion and TOH with n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atree-recursion-toh-algorithm) — Data Structure and Algorithm, chapter 5
- [TOH for 3 disks and recursion principle](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-3-disks-tree-principle) — Data Structure and Algorithm, chapter 5
- [Box trace and TOH recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abox-trace-toh-tree) — Data Structure and Algorithm, chapter 5
- [TOH algorithm and recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-algorithm-recursion-tree) — Data Structure and Algorithm, chapter 5, asked 2×
- [Solve TOH for 3 disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-3-disks-steps) — Data Structure and Algorithm, chapter 5, asked 2×
- [Recursion properties, Fibonacci, TOH algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-properties-fibonacci-toh) — Data Structure and Algorithm, chapter 5

## Related in other subjects

- [Set up recurrence for Tower of Hanoi](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-setup-recurrence) — Discrete Structure, chapter 3
- [Derive and solve Tower of Hanoi recurrence](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-derive-and-solve) — Discrete Structure, chapter 3