---
title: "TOH algorithm and recursion tree"
subject: "Data Structure and Algorithm"
chapter: 5
key: "semester_4/data_structure_and_algorithm:toh-algorithm-recursion-tree"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/toh-algorithm-recursion-tree
site: BCT Engineering
---

# TOH algorithm and recursion tree

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2069 Poush, 3+5 marks; 2070 Magh, 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-algorithm-recursion-tree
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

Write an algorithm for TOH problem. Hence find all solutions for three disks from your algorithm, showing recursion tree for the same.

## Short answer

Algorithm TOH(n, from, to, aux): if n=1, move disk from to; else TOH(n-1, from, aux, to); move disk n; TOH(n-1, aux, to, from). For n=3, the recursion tree has root TOH(3,A,C,B) with left child TOH(2,A,B,C) and right child TOH(2,B,C,A); nodes at depth n-1 execute moves in in-order, producing 7 moves.

## Answer

#### Algorithm TOH(n, from, to, aux)
1. If n = 1: move disk 1 from `from` to `to`; return.
2. TOH(n-1, from, aux, to).
3. Move disk n from `from` to `to`.
4. TOH(n-1, aux, to, from).

```c
#include <stdio.h>

/* move n disks from 'from' to 'to' using 'aux' */
void toh(int n, char from, char to, char aux) {
    if (n == 1) {                                   /* base case */
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    toh(n - 1, from, aux, to);                      /* step 1 */
    printf("Move disk %d from %c to %c\n", n, from, to);   /* step 2 */
    toh(n - 1, aux, to, from);                      /* step 3 */
}

int main(void) {
    toh(3, 'A', 'C', 'B');
    return 0;
}
```

#### All solution steps for three disks (call TOH(3, A, C, B))
Output (verified by running the algorithm):
```text
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from 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 |

#### Recursion tree for 3 disks
Each node is a call TOH(n, from, to, aux). A move is performed at each node between its left and right subtree calls.

```text
                    TOH(3,A,C,B)
                  [4: disk 3 A->C]
              /                      \
     TOH(2,A,B,C)                TOH(2,B,C,A)
    [2: disk 2 A->B]            [6: disk 2 B->C]
      /         \                 /         \
 (1,A,C,B)   (1,C,B,A)      (1,B,A,C)   (1,A,C,B)
 [1: A->C]   [3: C->B]      [5: B->A]   [7: A->C]
```
Moves are printed in in-order (left subtree, node, right subtree): 1 to 7.

The tree has 2³ − 1 = 7 nodes, so 7 moves are made. Number of calls for n disks = 2ⁿ − 1, and the depth of the tree is n.

## Check yourself

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

1. In the TOH algorithm, what happens when n = 1?
   A. Two recursive calls with n = 0 are made
   B. The function prints nothing
   C. All pegs are swapped
   D. Disk 1 is moved from 'from' to 'to' and the function returns
   Answer: D. n = 1 is the base case where the move is done directly without recursion. (Key point: Base case)

2. In what order are moves performed in the recursion tree?
   A. In-order: left subtree, node's move, right subtree
   B. Pre-order: node's move first
   C. Post-order: node's move last
   D. Level by level
   Answer: A. The move for disk n happens between the two recursive calls, so it is in-order. (Key point: Move order in tree)

3. How many nodes (calls) does the recursion tree for 3 disks have, and what is its depth?
   A. 8 nodes; depth 4
   B. 7 nodes; depth 3
   C. 6 nodes; depth 3
   D. 7 nodes; depth 7
   Answer: B. Calls = 2^n - 1 = 7 and levels = n = 3. (Key point: Tree size)

4. What is the move at the root TOH(3,A,C,B)?
   A. Disk 1 from A to C
   B. Disk 3 from A to B
   C. Disk 3 from A to C
   D. Disk 2 from A to B
   Answer: C. The root moves the largest disk from source to destination, it is move 4 overall. (Key point: Middle move)

## 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
- [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 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
- [TOH problem with solution for n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-n-disks-solution) — Data Structure and Algorithm, chapter 5, asked 2×
- [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
- [Recursion tree for Tower of Hanoi, 4 disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-recursion-tree-4-disks) — Data Structure and Algorithm, chapter 5