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.