Tower of Hanoi Problem in DSA Javascript - Execution Trace

Concept Flow - Tower of Hanoi Problem

Start with all disks on Source

↓

Move top n-1 disks from Source to Auxiliary

↓

Move largest disk from Source to Destination

↓

Move n-1 disks from Auxiliary to Destination

↓

All disks moved to Destination in order

The problem moves disks between three rods using recursion: move smaller disks to auxiliary, move largest disk to destination, then move smaller disks from auxiliary to destination.

Execution Sample

DSA Javascript

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

This recursive function prints the steps to move n disks from source to destination using auxiliary rod.

Execution Table

Step	Operation	Disks Moved	From Rod	To Rod	Aux Rod	Visual State
1	Move disk 1	1	A	C	B	A:[3,2], B:[], C:[1]
2	Move disk 2	2	A	B	C	A:[3], B:[2], C:[1]
3	Move disk 1	1	C	B	A	A:[3], B:[2,1], C:[]
4	Move disk 3	3	A	C	B	A:[], B:[2,1], C:[3]
5	Move disk 1	1	B	A	C	A:[1], B:[2], C:[3]
6	Move disk 2	2	B	C	A	A:[1], B:[], C:[3,2]
7	Move disk 1	1	A	C	B	A:[], B:[], C:[3,2,1]
Exit	All disks moved	-	-	-	-	A:[], B:[], C:[3,2,1]

💡 All disks moved from rod A to rod C in correct order

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Rod A	[3,2,1]	[3,2]	[3]	[3]	[]	[1]	[1]	[]	[]
Rod B	[]	[]	[2]	[2,1]	[2,1]	[2]	[]	[]	[]
Rod C	[]	[1]	[1]	[]	[3]	[3]	[3,2]	[3,2,1]	[3,2,1]

Key Moments - 3 Insights

Why do we move n-1 disks to auxiliary before moving the largest disk?

Because the largest disk can only be moved when the smaller disks above it are out of the way, as shown in steps 1-3 in the execution_table.

Why do we move disks back from auxiliary to destination after moving the largest disk?

Because after placing the largest disk on destination, the smaller disks on auxiliary must be moved on top of it to complete the tower, as shown in steps 5-7.

Why is the base case n=1 important?

Because when only one disk remains, it can be moved directly without recursion, stopping the recursive calls, as shown in step 1.

Visual Quiz - 3 Questions

Look at the execution_table, after which step is the largest disk first moved to rod C?

A Step 4

B Step 3

C Step 5

D Step 7

💡 Hint

Check the 'Operation' and 'To Rod' columns in execution_table rows.

According to variable_tracker, what is the state of rod B after step 3?

A [2]

B [2,1]

C []

D [1]

💡 Hint

Look at the 'Rod B' row under 'After Step 3' in variable_tracker.

If we change the number of disks to 2, how many total moves will the execution_table show?

A 1

B 7

C 3

D 4

💡 Hint

Recall that minimum moves for n disks is 2^n - 1; check execution_table steps for n=3.

Concept Snapshot

Tower of Hanoi moves n disks from source to destination using auxiliary.
Move n-1 disks to auxiliary, move largest disk to destination, then move n-1 disks from auxiliary to destination.
Base case: move single disk directly.
Minimum moves: 2^n - 1.
Recursive calls handle smaller problems.
Visualize rods as stacks of disks.

Full Transcript

The Tower of Hanoi problem moves disks from one rod to another using an auxiliary rod. The recursive solution moves n-1 disks to auxiliary, moves the largest disk to destination, then moves n-1 disks from auxiliary to destination. The base case moves one disk directly. The execution table shows each move step with rods' states. Variable tracker shows rods' contents after each step. Key moments clarify why recursion splits the problem and the importance of the base case. The quiz tests understanding of steps and rod states. The snapshot summarizes the recursive approach and minimum moves.

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