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.