Zig Zag

 

1. Here are a few sets of inputs and outputs for your reference

Input1 -> 1

Output1 -> 111

Input2 -> 2

Output2 -> 211121112

Input2 -> 3

Output3 -> 3 21112111232111211123

2. Figure out the pattern and complete the recursive function pzz to achieve the above for any positive

number n.

Input Format

A number n

Output Format

As discussed in point 1 of description

package jan27;

public class ZigZag {
    public static void main(String[] args) {

        int n = 2;

        pzz(n); // EXPECTATION
    }

    /**
     * Prints numbers in a zig-zag recursive pattern:
     * - Prints n three times: pre-order, in-order, and post-order
     * - Calls itself twice with n-1
     *
     * Time Complexity: O(2^n)
     *  - Each call makes 2 recursive calls, doubling calls at each level
     *  - Total calls grow exponentially with n
     *
     * Space Complexity: O(n)
     *  - Maximum recursion depth is n
     */
    private static void pzz(int n) {
        if (n == 0) return;

        // WORK: pre-order
        System.out.print(n + " ");

        // FAITH
        pzz(n - 1);

        // WORK: in-order
        System.out.print(n + " ");

        // FAITH
        pzz(n - 1);

        // WORK: post-order
        System.out.print(n + " ");
    }
}

Case
Time Complexity
Space Complexity
Explanation
Best Case
O(2^n)
O(n)
Recursive calls always happen twice, recursion depth is n
Average Case
O(2^n)
O(n)
Same as best case, recursion structure doesn’t change
Worst Case
O(2^n)
O(n)
Same as best case, all calls are made