Tower of Hanoi Problem in DSA C

Mental Model

Move disks one by one from one peg to another, never placing a bigger disk on a smaller one, until all disks are moved to the target peg.

Analogy: Imagine moving a stack of different sized plates from one table to another using a spare table, but you can only move one plate at a time and never put a bigger plate on top of a smaller one.

Source Peg (A): 3 2 1 (1 is smallest on top)
Aux Peg (B): empty
Target Peg (C): empty

Dry Run Walkthrough

Input: 3 disks on peg A, move all to peg C using peg B

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 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 free largest disk

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 peg B

Step 4: Move disk 3 from A to C

A: 
B: 2 1
C: 3 ↑

Why: Move largest disk to target peg

Step 5: Move disk 1 from B to A

A: 1 ↑
B: 2
C: 3

Why: Free 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 on target peg

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 <stdio.h>

void towerOfHanoi(int n, char source, char target, char auxiliary) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, target);
        return;
    }
    towerOfHanoi(n - 1, source, auxiliary, target); // move n-1 disks to auxiliary
    printf("Move disk %d from %c to %c\n", n, source, target); // move nth disk to target
    towerOfHanoi(n - 1, auxiliary, target, source); // move n-1 disks from auxiliary to target
}

int main() {
    int n = 3;
    printf("Tower of Hanoi moves for %d disks:\n", n);
    towerOfHanoi(n, 'A', 'C', 'B');
    return 0;
}

if (n == 1) {

base case: move single disk directly

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

move top n-1 disks to auxiliary peg

printf("Move disk %d from %c to %c\n", n, source, target);

move largest disk to target peg

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

move n-1 disks from auxiliary to target peg

Output

Tower of Hanoi moves for 3 disks:

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 the number of moves doubles with each additional disk

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

vs Alternative: No simpler approach exists; this is the minimal number of moves required

Edge Cases

n = 1 (single disk)

Directly moves the single disk from source to target

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 == 0) { return; }

When to Use This Pattern

When you see a problem about moving disks or items between pegs with size constraints, use the Tower of Hanoi pattern because it solves the problem with minimal moves using recursion.

Common Mistakes

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

Mistake: Not correctly swapping roles of pegs in recursive calls
Fix: Carefully pass pegs in correct order for each recursive call to maintain rules

Summary

It solves the problem of moving disks between pegs following size rules using recursion.

Use it when you need to move stacked items with constraints on order and size.

The key insight is breaking the problem into moving smaller stacks recursively 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 recursive function signature in C for solving Tower of Hanoi?

easy

A. void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod);

B. int towerOfHanoi(int n, char from_rod, char to_rod);

C. void towerOfHanoi(int n, int from_rod, int to_rod);

D. void towerOfHanoi(int n, char from_rod, char to_rod);

Solution

1. Step 1: Identify parameters needed for Tower of Hanoi

   We need number of disks and names of three rods: source, destination, auxiliary.

2. Step 2: Check function signature matching these parameters

   void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod); has int n and three char rods, matching the problem requirements.

3. Final Answer:

   void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod); -> Option A

4. Quick Check:

   Function needs 3 rods and disk count [OK]

Hint: Tower of Hanoi needs 3 rods as parameters [OK]

Common Mistakes:

• Missing auxiliary rod parameter
• Using int instead of char for rods
• Returning int instead of void

3. What will be the output of the following C code snippet for Tower of Hanoi with 2 disks?

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
  if (n == 1) {
    printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
    return;
  }
  towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
  printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
  towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

int main() {
  towerOfHanoi(2, 'A', 'C', 'B');
  return 0;
}

medium

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

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

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

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

Solution

1. Step 1: Trace recursive calls for n=2

   First move disk 1 from A to B, then disk 2 from A to C, then disk 1 from B to C.

2. Step 2: Match output with options

   Move disk 1 from rod A to rod B Move disk 2 from rod A to rod C Move disk 1 from rod B to rod C matches the exact sequence of moves printed by the code.

3. Final Answer:

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

4. Quick Check:

   Recursive moves for 2 disks = Move disk 1 from rod A to rod B Move disk 2 from rod A to rod C Move disk 1 from rod B to rod C [OK]

Hint: For 2 disks, move smaller disk to aux first [OK]

Common Mistakes:

• Swapping auxiliary and destination rods
• Printing moves in wrong order
• Confusing disk numbers

4. Identify the error in the following Tower of Hanoi C function and select the correct fix:

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
  if (n == 0) {
    return;
  }
  towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
  printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
  towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

medium

A. Change base case condition to if (n == 1) instead of if (n == 0)

B. Add else before recursive calls

C. Change printf to print n-1 instead of n

D. Swap aux_rod and to_rod in recursive calls

Solution

1. Step 1: Analyze base case condition

   Base case should stop recursion when n == 1, not 0, to print the last move.

2. Step 2: Understand effect of current base case

   With n == 0, no moves are printed for the smallest disk, causing no output.

3. Final Answer:

   Change base case condition to if (n == 1) instead of if (n == 0) -> Option A

4. Quick Check:

   Base case must be n == 1 to print moves [OK]

Hint: Base case must be n == 1 to print last move [OK]

Common Mistakes:

• Using n == 0 as base case
• Changing print statement unnecessarily
• Swapping rods incorrectly

5. You want to solve Tower of Hanoi for 4 disks but print only the moves where disk 1 is moved. Which modification to the recursive function is correct?

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
  if (n == 1) {
    printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
    return;
  }
  towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
  printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
  towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

hard

A. Remove all recursive calls except for n == 1 case

B. Add condition to print only if n == 1 inside the function

C. Print all moves but filter disk 1 moves outside the function

D. Change base case to n == 0 and print only disk 1 moves

Solution

1. Step 1: Understand requirement to print only disk 1 moves

   We must print moves only when disk number is 1 inside the recursive function.

2. Step 2: Modify print statements accordingly

   Keep recursive calls intact but print only when n == 1, skipping other prints.

3. Final Answer:

   Add condition to print only if n == 1 inside the function -> Option B

4. Quick Check:

   Print condition inside recursion for disk 1 only [OK]

Hint: Print moves only when disk number is 1 inside recursion [OK]

Common Mistakes:

• Removing recursive calls breaks solution
• Filtering outside loses recursion context
• Changing base case incorrectly