Tower of Hanoi Problem in DSA Typescript

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: [3,2,1] -> Auxiliary: [] -> Destination: []
Disks are stacked largest (3) at bottom to smallest (1) at top.

Dry Run Walkthrough

Input: 3 disks on Source peg, move all to Destination peg using Auxiliary peg

Goal: Move all disks from Source to Destination following the rules

Step 1: Move disk 1 from Source to Destination

Source: [3,2]
Auxiliary: []
Destination: [1]

Why: Smallest disk moves first to free bigger disks

Step 2: Move disk 2 from Source to Auxiliary

Source: [3]
Auxiliary: [2]
Destination: [1]

Why: Move next bigger disk to free the largest disk

Step 3: Move disk 1 from Destination to Auxiliary

Source: [3]
Auxiliary: [2,1]
Destination: []

Why: Place smaller disk on top of bigger disk on Auxiliary

Step 4: Move disk 3 from Source to Destination

Source: []
Auxiliary: [2,1]
Destination: [3]

Why: Largest disk moves to Destination

Step 5: Move disk 1 from Auxiliary to Source

Source: [1]
Auxiliary: [2]
Destination: [3]

Why: Free disk 2 by moving smaller disk back

Step 6: Move disk 2 from Auxiliary to Destination

Source: [1]
Auxiliary: []
Destination: [3,2]

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

Step 7: Move disk 1 from Source to Destination

Source: []
Auxiliary: []
Destination: [3,2,1]

Why: Place smallest disk on top to complete

Result:

Source: []
Auxiliary: []
Destination: [3,2,1]
All disks moved to Destination in correct order

Annotated Code

DSA Typescript

class TowerOfHanoi {
  static moveDisks(n: number, source: string, destination: string, auxiliary: string): void {
    if (n === 0) return;
    // Move n-1 disks from source to auxiliary
    TowerOfHanoi.moveDisks(n - 1, source, auxiliary, destination);
    // Move nth disk from source to destination
    console.log(`Move disk ${n} from ${source} to ${destination}`);
    // Move n-1 disks from auxiliary to destination
    TowerOfHanoi.moveDisks(n - 1, auxiliary, destination, source);
  }
}

// Driver code
const disks = 3;
TowerOfHanoi.moveDisks(disks, 'Source', 'Destination', 'Auxiliary');

if (n === 0) return;

stop recursion when no disks to move

TowerOfHanoi.moveDisks(n - 1, source, auxiliary, destination);

move top n-1 disks to auxiliary peg

console.log(`Move disk ${n} from ${source} to ${destination}`);

move largest disk to destination peg

TowerOfHanoi.moveDisks(n - 1, auxiliary, destination, source);

move n-1 disks from auxiliary to destination peg

Output

Move disk 1 from Source to Destination

Move disk 2 from Source to Auxiliary

Move disk 1 from Destination to Auxiliary

Move disk 3 from Source to Destination

Move disk 1 from Auxiliary to Source

Move disk 2 from Auxiliary to Destination

Move disk 1 from Source to Destination

Complexity Analysis

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

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

0 disks

No moves are made, function returns immediately

DSA Typescript

if (n === 0) return;

1 disk

Single move from source to destination is printed

DSA Typescript

console.log(`Move disk ${n} from ${source} to ${destination}`);

When to Use This Pattern

When you see a problem requiring moving stacked items with size constraints and minimal moves, reach for the Tower of Hanoi pattern because it uses recursion to break down the problem into smaller subproblems.

Common Mistakes

Mistake: Forgetting to swap auxiliary and destination pegs in recursive calls
Fix: Carefully pass pegs in correct order to recursive calls to maintain rules

Mistake: Not handling base case n=0, causing infinite recursion
Fix: Add base case check if n === 0 to stop recursion

Summary

It moves disks between pegs following size and move rules using recursion.

Use it when you need to solve problems that involve moving stacked items with constraints.

The key insight is breaking the problem into moving smaller stacks recursively.