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.

Practice

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

easy

A. 6

B. 7

C. 8

D. 9

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 B

4. Quick Check:

   2^3 - 1 = 7 [OK]

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

Common Mistakes:

• Forgetting to subtract 1
• Using n instead of 2^n
• Confusing moves with disks

2. Which of the following is the correct TypeScript function signature for solving Tower of Hanoi recursively?

easy

A. function towerOfHanoi(n: number, from: string, to: string, aux: string): void

B. function towerOfHanoi(n: string, from: number, to: number, aux: number): number

C. function towerOfHanoi(n: number, from: number, to: number): void

D. function towerOfHanoi(n: number): string

Solution

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

   We need number of disks (number), source peg (string), destination peg (string), and auxiliary peg (string).

2. Step 2: Match with function signature

   function towerOfHanoi(n: number, from: string, to: string, aux: string): void matches all parameters with correct types and returns void as it prints moves.

3. Final Answer:

   function towerOfHanoi(n: number, from: string, to: string, aux: string): void -> Option A

4. Quick Check:

   Correct parameters and return type [OK]

Hint: Check parameter types and count carefully [OK]

Common Mistakes:

• Using wrong parameter types
• Missing auxiliary peg parameter
• Wrong return type

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

function towerOfHanoi(n: number, from: string, to: string, aux: string): void {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}
towerOfHanoi(2, 'A', 'C', 'B');

medium

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

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

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

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

Solution

1. Step 1: Trace first recursive call with n=2

   Call towerOfHanoi(1, 'A', 'B', 'C') prints "Move disk 1 from A to B".

2. Step 2: Print move for disk 2

   Prints "Move disk 2 from A to C".

3. Step 3: Trace second recursive call with n=1

   Call towerOfHanoi(1, 'B', 'C', 'A') prints "Move disk 1 from B to C".

4. Final Answer:

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

5. Quick Check:

   Follow recursion steps carefully [OK]

Hint: Follow recursion calls step-by-step [OK]

Common Mistakes:

• Mixing source and auxiliary pegs
• Printing moves in wrong order
• Confusing disk numbers

4. Identify the error in this Tower of Hanoi TypeScript function and select the fix:

function towerOfHanoi(n: number, from: string, to: string, aux: string): void {
  if (n === 0) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}

medium

A. Change base case to if (n === 1) and print move for disk 1

B. Change base case to if (n === 0) and remove print statement

C. Remove recursive calls and only print moves

D. Change print statement to print disk 0

Solution

1. Step 1: Analyze base case condition

   Base case should be when n equals 1, not 0, because disk numbering starts at 1.

2. Step 2: Fix base case and print statement

   Change if (n === 0) to if (n === 1) and print move for disk 1.

3. Final Answer:

   Change base case to if (n === 1) and print move for disk 1 -> Option A

4. Quick Check:

   Base case must handle smallest disk [OK]

Hint: Base case is n === 1, not zero [OK]

Common Mistakes:

• Using n === 0 as base case
• Printing move for disk 1 in wrong place
• Skipping base case

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

hard

A. Print all moves and filter disk 1 moves after recursion

B. Remove all recursive calls except for n=1

C. Add condition to print only if disk number is 1 inside the print statement

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

Solution

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

   We must keep recursion intact but print moves only when disk number is 1.

2. Step 2: Modify print statement with condition

   Add if (n === 1) before printing move to filter only disk 1 moves.

3. Final Answer:

   Add condition to print only if disk number is 1 inside the print statement -> Option C

4. Quick Check:

   Filter print, keep recursion [OK]

Hint: Use if condition inside print to filter moves [OK]

Common Mistakes:

• Removing recursive calls breaks solution
• Filtering moves after recursion wastes time
• Changing base case incorrectly