Tower of Hanoi Problem in DSA Java

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 third empty 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: []
(3 is biggest disk at bottom, 1 is smallest 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: Start by moving the smallest disk to free space

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 auxiliary peg to free the largest disk

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 by moving smallest disk back to Peg A

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 largest disk on Peg C

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

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

Why: Move smallest disk on top to complete the stack

Result:

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

Annotated Code

DSA Java

public class TowerOfHanoi {

    public static void solve(int n, char fromPeg, char toPeg, char auxPeg) {
        if (n == 1) {
            System.out.println("Move disk 1 from peg " + fromPeg + " to peg " + toPeg);
            return;
        }
        solve(n - 1, fromPeg, auxPeg, toPeg); // move top n-1 disks to auxiliary peg
        System.out.println("Move disk " + n + " from peg " + fromPeg + " to peg " + toPeg); // move largest disk
        solve(n - 1, auxPeg, toPeg, fromPeg); // move n-1 disks from auxiliary to target peg
    }

    public static void main(String[] args) {
        int disks = 3;
        System.out.println("Tower of Hanoi solution for " + disks + " disks:");
        solve(disks, 'A', 'C', 'B');
    }
}

if (n == 1) {

base case: move single disk directly

solve(n - 1, fromPeg, auxPeg, toPeg);

move top n-1 disks to auxiliary peg

System.out.println("Move disk " + n + " from peg " + fromPeg + " to peg " + toPeg);

move largest disk to target peg

solve(n - 1, auxPeg, toPeg, fromPeg);

move n-1 disks from auxiliary peg to target peg

Output

Tower of Hanoi solution for 3 disks:

Move disk 1 from peg A to peg C

Move disk 2 from peg A to peg B

Move disk 1 from peg C to peg B

Move disk 3 from peg A to peg C

Move disk 1 from peg B to peg A

Move disk 2 from peg B to peg C

Move disk 1 from peg A to peg C

Complexity Analysis

Time: O(2^n) because the number of moves doubles with each additional disk

Space: O(n) due to recursion call stack depth equal to number of disks

vs Alternative: No simpler algorithm exists; this is the minimal number of moves required

Edge Cases

n = 1 (single disk)

Directly moves the single disk from source to target without recursion

DSA Java

if (n == 1) {

n = 0 (no disks)

Not explicitly handled; function returns immediately without moves

DSA Java

if (n == 0) return;

When to Use This Pattern

When you see a problem requiring moving stacked items with size constraints and minimal moves, reach for the Tower of Hanoi pattern because it uses recursion to break down the problem into smaller moves.

Common Mistakes

Mistake: Trying to move multiple disks at once instead of one at a time
Fix: Ensure the recursive calls move only one disk at a time and follow the rules

Mistake: Placing a bigger disk on top of a smaller disk
Fix: Follow the rule strictly by moving disks in correct order using recursion

Summary

It solves the problem of moving disks between pegs following size and move rules.

Use it when you need to move stacked items with constraints on order and size.

The key insight is breaking the problem into moving smaller stacks recursively.

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