Tree Diagram

fun(3)
|
|--> Pre: 3
|--> fun(2)
|    |
|    |--> Pre: 2
|    |--> fun(1)
|    |    |--> Base: 1
|    |--> In: 2
|    |--> fun(0)
|    |    |--> Base: 0
|    |--> Post: 2
|--> In: 3
|--> fun(1)
|    |--> Base: 1
|--> Post: 3

package jan27;

public class TreeDiag {
    public static void main(String[] args) {
        int n = 5;
        fun(n);
    }

    /**
     * Time Complexity: O(2^n)
     * Each call makes 2 recursive calls (fun(n-1) and fun(n-2)),
     * leading to an exponential number of total calls, like a binary tree.

     * Space Complexity: O(n)
     * The maximum depth of recursion (call stack) comes from the fun(n-1) path,
     * which can go as deep as n levels before returning.
     */
    private static void fun(int n) {
        if (n <= 1) {
            System.out.println("Base: " + n);
            return;
        }

        System.out.println("Pre: " + n);
        fun(n - 1);             // First recursive call
        System.out.println("In: " + n);
        fun(n - 2);             // Second recursive call
        System.out.println("Post: " + n);
    }
}


📊 Summary Table:
Complexity Type
Value
Explanation
Time Complexity
O(2^n)
Because of two recursive calls per function call (binary recursion tree)
Space Complexity
O(n)
Maximum depth of recursion is linear (fun(n-1) calls before any return)