Tower of Hanoi Problem in DSA Java - 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 Java

void hanoi(int n, char src, char aux, char dest) {
  if (n == 1) {
    System.out.println("Move disk 1 from " + src + " to " + dest);
    return;
  }
  hanoi(n-1, src, dest, aux);
  System.out.println("Move disk " + n + " from " + src + " to " + dest);
  hanoi(n-1, aux, src, dest);
}

This code moves n disks from source to destination using auxiliary recursively.

Execution Table

Step	Operation	Disks Moved	Source Peg	Auxiliary Peg	Destination Peg	Visual State
1	Move disk 1 from A to C	Disk 1	A	B	C	A: [3,2] B: [] C: [1]
2	Move disk 2 from A to B	Disk 2	A	B	C	A: [3] B: [2] C: [1]
3	Move disk 1 from C to B	Disk 1	A	B	C	A: [3] B: [2,1] C: []
4	Move disk 3 from A to C	Disk 3	A	B	C	A: [] B: [2,1] C: [3]
5	Move disk 1 from B to A	Disk 1	A	B	C	A: [1] B: [2] C: [3]
6	Move disk 2 from B to C	Disk 2	A	B	C	A: [1] B: [] C: [3,2]
7	Move disk 1 from A to C	Disk 1	A	B	C	A: [] B: [] C: [3,2,1]

💡 All disks moved from Source (A) to Destination (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
Source Peg (A)	[3,2,1]	[3,2]	[3]	[3]	[]	[1]	[]	[]
Auxiliary Peg (B)	[]	[]	[2]	[2,1]	[2,1]	[2]	[]	[]
Destination Peg (C)	[]	[1]	[1]	[]	[3]	[3]	[3,2]	[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 cannot be placed on a smaller disk, so we first clear the way by moving smaller disks to auxiliary (see steps 1-3 in 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 stack (see steps 5-7 in execution_table).

How does the recursion stop?

When n equals 1, we directly move the single disk from source to destination without further recursion (step 1 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the state of the pegs after Step 4?

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

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

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

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

💡 Hint

Check the Visual State column for Step 4 in execution_table

At which step is the largest disk moved from Source to Destination?

A Step 3

B Step 4

C Step 5

D Step 7

💡 Hint

Look for the operation mentioning disk 3 moving from A to C in execution_table

If we had 2 disks instead of 3, how many total moves would be made?

A 7

B 4

C 3

D 1

💡 Hint

Recall Tower of Hanoi moves count is 2^n - 1; check variable_tracker for n=3 moves

Concept Snapshot

Tower of Hanoi:
- Move n disks from Source to Destination using Auxiliary
- Move n-1 disks to Auxiliary
- Move largest disk to Destination
- Move n-1 disks from Auxiliary to Destination
- Total moves = 2^n - 1
- Recursive base case: n=1, move disk directly

Full Transcript

The Tower of Hanoi problem moves disks from one peg to another following rules: only one disk moves at a time, and a larger disk cannot be placed on a smaller disk. The recursive solution moves n-1 disks to an auxiliary peg, moves the largest disk to the destination peg, then moves the n-1 disks from auxiliary to destination. The execution table shows each move step-by-step with the state of pegs. The variable tracker shows how disks shift among pegs after each move. Key moments clarify why the recursion moves smaller disks first and how it stops at the base case. The visual quiz tests understanding of peg states and move counts. The snapshot summarizes the recursive approach and move count formula.

Practice

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

easy

A. 9

B. 6

C. 8

D. 7

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 D

4. Quick Check:

   2^3 - 1 = 7 [OK]

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

Common Mistakes:

• Using n instead of 2^n - 1
• Calculating 2*n - 1 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 Java?

easy

A. if (n < 0) return;

B. if (n == 1) return;

C. if (n == 0) return;

D. if (n > 1) return;

Solution

1. Step 1: Identify base case for recursion

   Base case stops recursion when no disks are left to move, i.e., n == 0.

2. Step 2: Check each option

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

3. Final Answer:

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

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 which causes extra calls
• Using negative values as base case
• Returning when n > 1 which stops too early

3. What will be the output sequence of moves for Tower of Hanoi with 2 disks from source A to destination C using auxiliary B?

medium

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

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

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

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

Solution

1. Step 1: Understand move sequence for 2 disks

   Move smaller disk 1 from source A to auxiliary B.

2. Step 2: Move larger disk 2 from source A to destination C, then move disk 1 from B to C

   This completes the transfer following rules.

3. Final Answer:

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

4. Quick Check:

   Correct move order for 2 disks [OK]

Hint: Move smaller disk first to auxiliary, then largest to destination [OK]

Common Mistakes:

• Swapping disk numbers in moves
• Moving larger disk before smaller disk
• Incorrect order of moves

4. Identify the error in this Tower of Hanoi recursive function snippet:

void towerOfHanoi(int n, char from, char to, char aux) {
  if (n == 1) {
    System.out.println("Move disk 1 from " + from + " to " + to);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  System.out.println("Move disk " + n + " from " + from + " to " + to);
  towerOfHanoi(n - 1, aux, to, from);
}

medium

A. Base case should be if (n == 0) instead of if (n == 1)

B. There is no error; the function is correct

C. The print statement should be before the first recursive call

D. The order of parameters in recursive calls is incorrect

Solution

1. Step 1: Analyze base case correctness

   Base case n == 1 means move the single disk directly, which is correct.

2. Step 2: Check recursive calls and print order

   First move n-1 disks from source to auxiliary, then move nth disk, then move n-1 disks from auxiliary to destination. This matches the Tower of Hanoi logic.

3. Final Answer:

   There is no error; the function is correct -> Option B

4. Quick Check:

   Function matches Tower of Hanoi recursion [OK]

Hint: Check base case and recursive call order carefully [OK]

Common Mistakes:

• Changing base case to n == 0 causing infinite recursion
• Swapping parameters in recursive calls
• Moving print statement incorrectly

5. If the Tower of Hanoi problem has 4 disks, what is the total number of moves and what is the move sequence for the first two moves from source A to destination C using auxiliary B?

hard

A. Total moves: 15\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from A to C

B. Total moves: 14\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from B to C

C. Total moves: 16\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from A to C

D. Total moves: 15\nFirst move: Move disk 1 from A to C\nSecond move: Move disk 2 from A to B

Solution

1. Step 1: Calculate total moves for 4 disks

   Total moves = 2^4 - 1 = 16 - 1 = 15 moves.

2. Step 2: Determine first two moves in sequence

   First move: Move smallest disk 1 from A to B (auxiliary). Second move: Move disk 2 from A to C (destination).

3. Final Answer:

   Total moves: 15\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from A to C -> Option A

4. Quick Check:

   2^4 - 1 = 15 and correct first moves [OK]

Hint: Use formula for moves and remember smallest disk moves first [OK]

Common Mistakes:

• Incorrect total moves calculation
• Swapping first two moves
• Confusing auxiliary and destination rods