---
title: "TOH problem with solution for n disks"
subject: "Data Structure and Algorithm"
chapter: 5
key: "semester_4/data_structure_and_algorithm:toh-n-disks-solution"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/toh-n-disks-solution
site: BCT Engineering
---

# TOH problem with solution for n disks

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2072 Magh, 5 marks; 2070 Bhadra, 5 marks (asked 2 times)
- Video: [Tower of Hanoi Problem - Made Easy](https://www.youtube.com/watch?v=q6RicK1FCUs) — Abdul Bari
- 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-n-disks-solution
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

Explain TOH problem with its solution for n disks.

## Short answer

Move n disks from source to destination using auxiliary with one disk per move and no larger on smaller. Solve recursively: move n-1 disks to auxiliary, move largest to destination, then move n-1 from auxiliary. The number of moves is 2^n - 1.

## Answer

#### The problem
Tower of Hanoi has three pegs (source A, auxiliary B, destination C) and n disks of different sizes stacked on A with the largest at the bottom. Move all disks to C under these rules:
1. Only one disk is moved at a time.
2. Only the top disk of a peg can be moved.
3. A larger disk may never be placed on a smaller one.

#### Recursive solution for n disks
To move n disks from A to C using B:
1. Move the top n-1 disks from A to B (using C as auxiliary).
2. Move the largest disk n from A to C.
3. Move the n-1 disks from B to C (using A as auxiliary).

Base case: one disk is moved directly. The same idea solves the smaller problems, so it is naturally recursive.

```c
void toh(int n, char from, char to, char aux) {
    if (n == 1) { printf("Move disk 1 from %c to %c\n", from, to); return; }
    toh(n - 1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    toh(n - 1, aux, to, from);
}
```

#### Number of moves
T(1) = 1 and T(n) = 2T(n-1) + 1, which gives **T(n) = 2ⁿ − 1**. Time complexity is O(2ⁿ).

| n | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| moves | 1 | 3 | 7 | 15 | 31 |

#### Example n = 3 (A to C)
| Move | Disk | From | To | Pegs after the move (A / B / C) |
|---|---|---|---|---|
| 1 | 1 | A | C | 3,2 / - / 1 |
| 2 | 2 | A | B | 3 / 2 / 1 |
| 3 | 1 | C | B | 3 / 2,1 / - |
| 4 | 3 | A | C | - / 2,1 / 3 |
| 5 | 1 | B | A | 1 / 2 / 3 |
| 6 | 2 | B | C | 1 / - / 3,2 |
| 7 | 1 | A | C | - / - / 3,2,1 |

Total 7 = 2³ − 1 moves (generated and checked with a program).

## Check yourself

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

1. Which move is NOT allowed in Tower of Hanoi?
   A. Placing a larger disk on a smaller disk
   B. Moving the top disk of a peg
   C. Moving one disk at a time
   D. Using the auxiliary peg
   Answer: A. A larger disk may never rest on a smaller one. (Key point: TOH rules)

2. To move n disks from A to C using B, what is the correct order?
   A. Move n-1 from A to C, move disk n A to B, move n-1 from C to B
   B. Move n-1 from A to B, move disk n A to C, move n-1 from B to C
   C. Move disk n A to B, then n-1 from A to C
   D. Move all n disks together to C
   Answer: B. The n-1 smaller disks go to the auxiliary peg, the largest moves, then the n-1 disks go on top of it. (Key point: Recursive solution)

3. What is the number of moves for n disks and the time complexity?
   A. n^2 moves; O(n^2)
   B. 2n - 1 moves; O(n)
   C. 2^n - 1 moves; O(2^n)
   D. 2^n moves; O(n log n)
   Answer: C. T(n) = 2T(n-1) + 1 with T(1) = 1 gives 2^n - 1. (Key point: Number of moves)

4. What is the base case of the TOH recursion?
   A. n = 0: move all disks
   B. n = 2: swap two disks
   C. n = 3: print the pegs
   D. n = 1: move the single disk directly
   Answer: D. With one disk no further subproblem is needed, so it is moved directly from source to destination. (Key point: Base case)

## Related in Data Structure and Algorithm

- [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×
- [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
- [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
- [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×
- [Recursion, Fibonacci and TOH](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-fibonacci-toh) — Data Structure and Algorithm, chapter 5

## Related in other subjects

- [Multipath inheritance problem and solution](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Amultipath-inheritance-problem) — Object Oriented Programming, chapter 6, asked 2×
- [Dining philosophers problem and solution](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adining-philosophers) — Operating System, chapter 3, asked 2×
- [Galerkin and collocation solution of an ODE](https://www.bctengineer.com/question.md?key=semester_8%2Ffinite_element_method%3Agalerkin-collocation-ode) — Finite Element Method, chapter 4
- [Data dependency problem in pipelining](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Adata-dependency) — Computer Organization and Architecture, chapter 4