Tower of Hanoi

Problem Link

Tower of Hanoi – GeeksforGeeks

Problem: Tower of Hanoi

Problem Statement

Given N disks, the objective is to move all the disks from source rod A to destination rod C using auxiliary rod B following these rules:

1. Only one disk can be moved at a time.

2. A disk can only be placed on top of a larger disk or an empty rod.

3. You can only move the top disk of a rod.

You need to print the steps and return the total number of moves.

Examples

Example 1
Input: N = 2
Output:

Move disk 1 from rod A to rod B  
Move disk 2 from rod A to rod C  
Move disk 1 from rod B to rod C  
Total moves: 3

Constraints

• 1 <= N <= 16

Intuition

This is a classic recursive problem. The core idea is:

• Move N - 1 disks from A to B

• Move the Nth (largest) disk from A to C

• Move N - 1 disks from B to C

This recursive breakdown naturally fits the Induction – Base Case – Hypothesis reasoning.

Induction – Base Case – Hypothesis Method

Function Signature

void toh(int N, char source, char destination, char auxiliary)

Base Case

If N == 1:

• We have only one disk to move.

• Move it directly from source to destination.

Move disk 1 from rod A to rod C

Hypothesis

Assume that we can move N - 1 disks from:

• Source → Auxiliary using Destination

Induction Step

To move N disks from A → C using B:

1. Move N-1 disks from A → B using C (recursively)

2. Move disk N from A → C

3. Move N-1 disks from B → C using A (recursively)

Code (Java)

class Hanoi {
    static int count = 0;

    public long toh(int N, int A, int C, int B) {
        count = 0; // reset global count for each call
        solve(N, A, C, B);
        return count;
    }

    private void solve(int N, int from, int to, int aux) {
        // Base Case
        if (N == 1) {
            System.out.println("move disk 1 from rod " + from + " to rod " + to);
            count++;
            return;
        }

        // Hypothesis and Induction
        solve(N - 1, from, aux, to);  // Step 1
        System.out.println("move disk " + N + " from rod " + from + " to rod " + to);  // Step 2
        count++;
        solve(N - 1, aux, to, from);  // Step 3
    }
}

Time and Space Complexity

• Time Complexity: O(2^N)

  • Each recursive call breaks into 2 subproblems + 1 move.

  • Total moves = 2^N - 1

• Space Complexity: O(N)

  • Due to recursion stack

Dry Run

Input: N = 2, A = 1, C = 3, B = 2

Call: toh(2, 1, 3, 2)

Step 1: move disk 1 from rod 1 to rod 2
Step 2: move disk 2 from rod 1 to rod 3
Step 3: move disk 1 from rod 2 to rod 3

Total moves = 3

Conclusion

Tower of Hanoi is one of the best problems to understand recursive tree structure and Induction – Base Case – Hypothesis strategy. It not only teaches recursion but also mathematical recurrence and elegant problem decomposition.