Tower of Hanoi

 

For this particular question, we only have the In - region. So, the code looks like :

package pep.Day7;

public class TowerOfHanoi {


    public static void main(String[] args) {
        int n = 3;
        char t1 = 'A';
        char t2 = 'B';
        char t3 = 'C';
        toh(n, t1, t2, t3);
    }

    private static void toh(int n, char t1, char t2, char t3) {
        if (n == 0)
            return; 
        toh(n - 1, t1, t3, t2);
        System.out.println(n + "[" + t1 + " -> " + t2 + "]");
        toh(n - 1, t3, t2, t1);

    }
}

Time complexity: O(2^n).

Space complexity: O(1)

There is no data structure used, thus no auxiliary space is used. Hence, space complexity is O(1). Note: if we talk about the recursion space then it would be O(n).