Tower of Hanoi Problem in DSA Typescript - Execution Trace

Concept Flow - Tower of Hanoi Problem

Start with all disks on Source

↓

Move 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

The Tower of Hanoi moves disks recursively: move smaller stacks to auxiliary, move largest disk, then move smaller stacks to destination.

Execution Sample

DSA Typescript

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 code prints the steps to move n disks from source to destination using auxiliary.

Execution Table

Step	Operation	Disks Moved	From Peg	To Peg	Visual State
1	Move disk 1	1	A	C	A: [3,2] B: [] C: [1]
2	Move disk 2	2	A	B	A: [3] B: [2] C: [1]
3	Move disk 1	1	C	B	A: [3] B: [2,1] C: []
4	Move disk 3	3	A	C	A: [] B: [2,1] C: [3]
5	Move disk 1	1	B	A	A: [1] B: [2] C: [3]
6	Move disk 2	2	B	C	A: [1] B: [] C: [3,2]
7	Move disk 1	1	A	C	A: [] B: [] C: [3,2,1]

💡 All disks moved from peg A to peg C following Tower of Hanoi rules.

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
Peg A	[3,2,1]	[3,2]	[3]	[3]	[]	[1]	[1]	[]
Peg B	[]	[]	[2]	[2,1]	[2,1]	[2]	[]	[]
Peg C	[]	[1]	[1]	[]	[3]	[3]	[3,2]	[3,2,1]
Disks Moved	0	1	2	1	3	1	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 can't we move a larger disk onto a smaller disk?

The rules forbid placing a bigger disk on a smaller one to keep the stack ordered; the visual state in each step shows disks stacked from largest at bottom to smallest on top.

How does recursion help solve the problem?

Recursion breaks the problem into smaller moves of n-1 disks, as seen in the repeated pattern of moving smaller stacks before and after moving the largest disk.

Visual Quiz - 3 Questions

Look at the execution_table, after which step is peg A empty?

A After Step 7

B After Step 4

C After Step 3

D After Step 2

💡 Hint

Check the 'Peg A' row in variable_tracker after each step.

At which step does the largest disk move from peg A to peg C?

A Step 3

B Step 5

C Step 4

D Step 7

💡 Hint

Look at the 'Operation' and 'Disks Moved' columns in execution_table.

If we had 2 disks instead of 3, how many steps would the execution_table have?

A 3 steps

B 5 steps

C 7 steps

D 1 step

💡 Hint

Recall the pattern: number of moves = 2^n - 1.

Concept Snapshot

Tower of Hanoi moves n disks from source to destination using auxiliary.
Rules: move one disk at a time, never place larger disk on smaller.
Recursive steps:
1) Move n-1 disks to auxiliary
2) Move largest disk to destination
3) Move n-1 disks from auxiliary to destination
Number of moves = 2^n - 1.

Full Transcript

The Tower of Hanoi problem involves moving disks from one peg to another following rules that only one disk moves at a time and a larger disk cannot be placed on a smaller disk. The solution uses recursion: first move n-1 disks to an auxiliary peg, then move the largest disk to the destination peg, and finally move the n-1 disks from auxiliary to destination. The execution table shows each move step-by-step with the state of all pegs. Variable tracking shows how the disks on each peg change after every move. Key moments clarify why the largest disk moves last and how recursion breaks down the problem. The visual quiz tests understanding of peg states and move counts. The quick snapshot summarizes the recursive approach and rules.

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