Tower of Hanoi Problem in DSA Javascript

Mental Model

Move all disks from one peg to another, one 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 spare table, moving only one plate at a time and never putting a bigger plate on top of a smaller one.

Peg A: [3, 2, 1]
Peg B: []
Peg C: []
(Disks are stacked with 3 at bottom, 1 at top)

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 Peg A to Peg C

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

Why: Smallest disk moves first to free up bigger disks

Step 2: Move disk 2 from Peg A to Peg B

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

Why: Move next bigger disk to spare peg to allow disk 1 to move

Step 3: Move disk 1 from Peg C to Peg B

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

Why: Place smallest disk on top of disk 2 on Peg B

Step 4: Move disk 3 from Peg A to Peg C

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

Why: Move largest disk to target peg

Step 5: Move disk 1 from Peg B to Peg A

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

Why: Free disk 2 to move to target peg

Step 6: Move disk 2 from Peg B to Peg C

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

Why: Move disk 2 on top of disk 3 on target peg

Step 7: Move disk 1 from Peg A to Peg C

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

Why: Place smallest disk on top of all disks on target peg

Result:

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

Annotated Code

DSA Javascript

class TowerOfHanoi {
  constructor() {
    this.moves = [];
  }

  moveDisks(n, fromPeg, toPeg, auxPeg) {
    if (n === 0) return;
    this.moveDisks(n - 1, fromPeg, auxPeg, toPeg); // move n-1 disks to auxiliary peg
    this.moves.push(`Move disk ${n} from ${fromPeg} to ${toPeg}`); // move nth disk to target peg
    this.moveDisks(n - 1, auxPeg, toPeg, fromPeg); // move n-1 disks from auxiliary to target peg
  }

  solve(n) {
    this.moves = [];
    this.moveDisks(n, 'A', 'C', 'B');
    return this.moves;
  }
}

const tower = new TowerOfHanoi();
const moves = tower.solve(3);
moves.forEach(move => console.log(move));

if (n === 0) return;

stop recursion when no disks to move

this.moveDisks(n - 1, fromPeg, auxPeg, toPeg);

move top n-1 disks to auxiliary peg

this.moves.push(`Move disk ${n} from ${fromPeg} to ${toPeg}`);

move largest disk to target peg

this.moveDisks(n - 1, auxPeg, toPeg, fromPeg);

move n-1 disks from auxiliary peg to target 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; brute force moves all disks one by one but still requires exponential moves

Edge Cases

0 disks

No moves are made, function returns immediately

DSA Javascript

if (n === 0) return;

1 disk

Only one move from source to target peg

DSA Javascript

this.moves.push(`Move disk ${n} from ${fromPeg} to ${toPeg}`);

When to Use This Pattern

When you see a problem about moving disks or items with size order constraints and limited moves, reach for Tower of Hanoi pattern because it uses recursion to break down the problem.

Common Mistakes

Mistake: Trying to move more than one disk at a time or placing bigger disk on smaller disk
Fix: Always move only one disk at a time and check the order before placing

Summary

It solves how to move disks between pegs following size and move rules.

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

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

B. 6

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 A

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 - 1
• Confusing number of disks with moves

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

easy

A. if (n < 0) return;

B. if (n === 1) moveDisk();

C. if (n > 1) return;

D. if (n === 0) return;

Solution

1. Step 1: Identify base case for recursion

   The recursion stops when there are no disks to move, i.e., n === 0.

2. Step 2: Check the options

   if (n === 0) return; correctly returns when n is 0, stopping recursion.

3. Final Answer:

   if (n === 0) return; -> Option D

4. Quick Check:

   Base case is n === 0 [OK]

Hint: Base case stops recursion at zero disks [OK]

Common Mistakes:

• Using n === 1 as base case incorrectly
• Not stopping recursion causing infinite calls
• Using invalid conditions like n < 0

3. What will be the output sequence of moves for 2 disks in the Tower of Hanoi problem using this code snippet?

function towerOfHanoi(n, from, to, aux) {
  if (n === 0) 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 2 from A to C"
"Move disk 1 from B to A"
"Move disk 2 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 A to B"
"Move disk 2 from A to C"
"Move disk 1 from B to C"

D. "Move disk 1 from A to C"
"Move disk 2 from A to B"
"Move disk 1 from C to 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 A to B" "Move disk 2 from A to C" "Move disk 1 from B to C" matches the exact sequence of moves printed by the code.

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 C

4. Quick Check:

   Correct move sequence for 2 disks = "Move disk 1 from A to B" "Move disk 2 from A to C" "Move disk 1 from B to C" [OK]

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

Common Mistakes:

• Mixing source and auxiliary rods
• Confusing disk numbers in moves
• Ignoring order of recursive calls

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

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

medium

A. Swap 'to' and 'aux' in the first recursive call

B. Change base case to n === 0

C. Remove the second recursive call

D. Add an extra console.log before recursion

Solution

1. Step 1: Analyze recursive calls

   The first recursive call should move n-1 disks from 'from' to 'aux' using 'to' as auxiliary, but here 'to' and 'aux' are swapped.

2. Step 2: Correct the argument order

   Swapping 'to' and 'aux' in the first recursive call fixes the logic to move disks correctly.

3. Final Answer:

   Swap 'to' and 'aux' in the first recursive call -> Option A

4. Quick Check:

   Correct recursive call order fixes error [OK]

Hint: Check recursive call parameters carefully [OK]

Common Mistakes:

• Mixing auxiliary and target rods
• Incorrect base case causing infinite recursion
• Removing necessary recursive calls

5. You want to solve the Tower of Hanoi problem for 4 disks but only want to print moves where disk 1 is moved. How would you modify this function?

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

hard

A. Change base case to n === 1 and print only then

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

C. Remove recursive calls and print only disk 1 move

D. Print all moves but filter output outside the function

Solution

1. Step 1: Understand the requirement

   We want to print moves only when disk 1 moves, but still perform all recursive calls to solve the problem.

2. Step 2: Modify print statement with condition

   Add an if condition to print only when n === 1, so other moves are not printed but recursion continues.

3. Final Answer:

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

4. Quick Check:

   Conditional print inside recursion solves problem [OK]

Hint: Use if (n === 1) to print selectively [OK]

Common Mistakes:

• Changing base case breaks recursion
• Removing recursive calls stops solution
• Filtering output outside misses recursion logic