Tower of Hanoi Problem in DSA C++

Mental Model

Move a stack of disks from one peg to another, one disk at a time, never placing a bigger disk on a smaller one.

Analogy: Imagine moving a stack of different sized plates from one table to another using a third empty table, moving only one plate at a time and never putting a bigger plate on top of a smaller one.

Source Peg (A): [3, 2, 1]
Aux Peg (B): []
Dest Peg (C): []

Disks are stacked with 3 at bottom, 1 at top.

Dry Run Walkthrough

Input: Move 3 disks from peg A to peg C using peg B as auxiliary

Goal: Move all disks from peg A to peg C following the rules

Step 1: Move disk 1 from A to C

A: [3, 2]
B: []
C: [1]

Why: Smallest disk moves first to free up bigger disks

Step 2: Move disk 2 from A to B

A: [3]
B: [2]
C: [1]

Why: Move next bigger disk to auxiliary peg to clear path

Step 3: Move disk 1 from C to B

A: [3]
B: [2, 1]
C: []

Why: Place smallest disk on top of disk 2 on auxiliary peg

Step 4: Move disk 3 from A to C

A: []
B: [2, 1]
C: [3]

Why: Move largest disk to destination peg

Step 5: Move disk 1 from B to A

A: [1]
B: [2]
C: [3]

Why: Free up disk 2 by moving smallest disk back to source

Step 6: Move disk 2 from B to C

A: [1]
B: []
C: [3, 2]

Why: Move disk 2 on top of largest disk at destination

Step 7: Move disk 1 from A to C

A: []
B: []
C: [3, 2, 1]

Why: Move smallest disk on top to complete the stack

Result:

A: []
B: []
C: [3, 2, 1]
All disks moved to peg C in correct order

Annotated Code

DSA C++

#include <iostream>
using namespace std;

void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << destination << endl;
        return;
    }
    towerOfHanoi(n - 1, source, auxiliary, destination); // move n-1 disks to auxiliary
    cout << "Move disk " << n << " from " << source << " to " << destination << endl; // move nth disk to destination
    towerOfHanoi(n - 1, auxiliary, destination, source); // move n-1 disks from auxiliary to destination
}

int main() {
    int n = 3;
    towerOfHanoi(n, 'A', 'B', 'C');
    return 0;
}

if (n == 1) {

base case: move single disk directly

towerOfHanoi(n - 1, source, auxiliary, destination);

move top n-1 disks to auxiliary peg

cout << "Move disk " << n << " from " << source << " to " << destination << endl;

move largest disk to destination peg

towerOfHanoi(n - 1, auxiliary, destination, source);

move n-1 disks from auxiliary to destination peg

Output

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

Complexity Analysis

Time: O(2^n) because each disk move doubles the number of moves needed

Space: O(n) due to recursion call stack depth equal to number of disks

vs Alternative: No simpler approach exists; iterative solutions simulate recursion but have similar exponential time

Edge Cases

n = 1 (single disk)

Directly moves the single disk from source to destination

DSA C++

if (n == 1) {

n = 0 (no disks)

No moves performed, function returns immediately (not explicitly handled but no output)

DSA C++

if (n == 1) {

When to Use This Pattern

When you see a problem requiring moving stacked items with size constraints and minimal moves, use the Tower of Hanoi pattern because it breaks the problem into smaller subproblems recursively.

Common Mistakes

Mistake: Trying to move multiple disks at once violating the rules
Fix: Always move only one disk at a time and never place a bigger disk on a smaller one

Mistake: Mixing up the order of pegs in recursive calls
Fix: Carefully follow the recursive pattern: move n-1 disks to auxiliary, move largest disk, then move n-1 disks to destination

Summary

Solves the problem of moving disks between pegs following size and move rules.

Use when you need to move stacked items with constraints recursively.

The key is breaking the problem into moving smaller stacks before moving the largest disk.

Practice

1. What is the minimum number of moves required to solve the Tower of Hanoi problem with 3 disks?

easy

A. 6

B. 5

C. 9

D. 7

Solution

1. Step 1: Understand the formula for minimum moves

   The minimum moves required for n disks is 2^n - 1.

2. Step 2: Calculate for 3 disks

   For 3 disks, minimum moves = 2^3 - 1 = 8 - 1 = 7.

3. Final Answer:

   7 -> Option D

4. Quick Check:

   2^3 - 1 = 7 [OK]

Hint: Use formula 2^n - 1 for minimum moves [OK]

Common Mistakes:

• Using n instead of 2^n - 1
• Calculating 2*n - 1 instead of 2^n - 1
• Confusing number of disks with moves

2. Which of the following is the correct base case condition in the Tower of Hanoi recursive function in C++?

easy

A. if (n == 1) move disk from source to destination;

B. if (n == 0) return;

C. if (n > 1) call recursive function;

D. if (n < 0) return;

Solution

1. Step 1: Identify the base case for recursion

   The base case is when there is only 1 disk to move, so move it directly.

2. Step 2: Check the options

   if (n == 1) move disk from source to destination; correctly states the base case: if (n == 1) move disk from source to destination.

3. Final Answer:

   if (n == 1) move disk from source to destination; -> Option A

4. Quick Check:

   Base case is n == 1 [OK]

Hint: Base case moves single disk directly [OK]

Common Mistakes:

• Using n == 0 as base case
• Not defining a base case
• Using incorrect condition like n < 0

3. What will be the output sequence of moves for Tower of Hanoi with 2 disks from peg A to peg C using peg B as auxiliary?

medium

A. Move disk 2 from A to C
Move disk 1 from A to B
Move disk 2 from C to B

B. Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

C. Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B

D. Move disk 2 from A to B
Move disk 1 from A to C
Move disk 2 from B to C

Solution

1. Step 1: Understand the recursive move sequence for 2 disks

   Move top disk (1) from A to B, move bottom disk (2) from A to C, then move disk (1) from B to C.

2. Step 2: Match the sequence with options

   Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C matches the correct sequence exactly.

3. Final Answer:

   Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C -> Option B

4. Quick Check:

   Correct move order for 2 disks [OK]

Hint: For 2 disks: move top to aux, bottom to dest, top to dest [OK]

Common Mistakes:

• Swapping auxiliary and destination pegs
• Moving larger disk before smaller disk
• Incorrect move order

4. Identify the error in the following Tower of Hanoi recursive function snippet in C++:

void towerOfHanoi(int n, char source, char aux, char dest) {
  if (n == 1) {
    cout << "Move disk 1 from " << source << " to " << dest << endl;
    return;
  }
  towerOfHanoi(n - 1, source, dest, aux);
  cout << "Move disk " << n << " from " << source << " to " << dest << endl;
  towerOfHanoi(n - 1, aux, source, dest);
}

medium

A. The order of auxiliary and destination pegs is swapped in recursive calls.

B. Base case condition should be n == 0 instead of n == 1.

C. The function does not print the moves correctly.

D. The function lacks a return statement after recursive calls.

Solution

1. Step 1: Analyze recursive calls parameters

   The first recursive call should move n-1 disks from source to auxiliary using destination as auxiliary, so parameters should be (n-1, source, dest, aux).

2. Step 2: Identify incorrect parameter order

   In the code, the first call uses (n-1, source, aux, dest) which swaps aux and dest incorrectly.

3. Final Answer:

   The order of auxiliary and destination pegs is swapped in recursive calls. -> Option A

4. Quick Check:

   Correct peg order is crucial in recursion [OK]

Hint: Check peg order in recursive calls carefully [OK]

Common Mistakes:

• Swapping auxiliary and destination pegs
• Wrong base case condition
• Missing return statements

5. If the Tower of Hanoi problem is modified to have 4 pegs instead of 3, which of the following statements is true about the minimum number of moves required to move n disks?

hard

A. It remains the same as 3 pegs: 2^n - 1 moves.

B. It is always more than 2^n - 1 moves due to extra peg.

C. It is always less than 2^n - 1 moves but no exact formula is known.

D. It is exactly n^2 moves for any n.

Solution

1. Step 1: Understand the classic formula for 3 pegs

   For 3 pegs, minimum moves = 2^n - 1.

2. Step 2: Consider 4 pegs case

   With 4 pegs, the problem is more complex; fewer moves than 2^n - 1 are possible but no simple closed formula exists.

3. Final Answer:

   It is always less than 2^n - 1 moves but no exact formula is known. -> Option C

4. Quick Check:

   4 pegs reduce moves but formula unknown [OK]

Hint: More pegs reduce moves but no simple formula [OK]

Common Mistakes:

• Assuming formula 2^n - 1 applies to 4 pegs
• Thinking more pegs increase moves
• Assuming quadratic moves for 4 pegs