🚀 Ready for Level 2?

// You already know this: Array with linear access
const numbers = [1, 3, 5, 7, 9];
console.log(numbers[2]); // Access by index: O(1)

// Now let's think hierarchically: Simple Tree Node
class SimpleTreeNode {
    value: number;
    left: SimpleTreeNode | null = null;
    right: SimpleTreeNode | null = null;
    
    constructor(value: number) {
        this.value = value;
    }
}

// Building a tree is like organizing a family tree
const root = new SimpleTreeNode(5);        // Parent
root.left = new SimpleTreeNode(3);         // Left child
root.right = new SimpleTreeNode(7);        // Right child
root.left.left = new SimpleTreeNode(1);    // Grandchild
root.left.right = new SimpleTreeNode(4);   // Grandchild

// Tree traversal is like visiting family members in order
function visitInOrder(node: SimpleTreeNode | null): void {
    if (node === null) return;
    
    visitInOrder(node.left);    // Visit left family first
    console.log(node.value);    // Visit current person
    visitInOrder(node.right);   // Visit right family last
}

// This prints: 1, 3, 4, 5, 7 (sorted order!)
visitInOrder(root);
                                    

// You already know this: Linear Search (check every element)
function linearSearch(arr: number[], target: number): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1; // Not found
}

// Time complexity: O(n) - might check every element

// Now the smarter way: Binary Search (eliminate half each time)
function binarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid; // Found it!
        } else if (arr[mid] < target) {
            left = mid + 1; // Target is in right half
        } else {
            right = mid - 1; // Target is in left half
        }
    }
    
    return -1; // Not found
}

// Time complexity: O(log n) - eliminates half each time

// Example: Finding 7 in [1, 3, 5, 7, 9, 11, 13]
const sortedArray = [1, 3, 5, 7, 9, 11, 13];

console.log("Linear search:", linearSearch(sortedArray, 7));  // Checks: 1,3,5,7 (4 steps)
console.log("Binary search:", binarySearch(sortedArray, 7)); // Checks: 7 (1 step!)
                                    

// You already know this: Simple Recursion (Fibonacci)
function fibonacciNaive(n: number): number {
    if (n <= 1) return n;
    return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);
}

// Problem: Recalculates the same values many times!
// fib(5) = fib(4) + fib(3)
// fib(4) = fib(3) + fib(2)  <- fib(3) calculated again!

// Solution: Dynamic Programming (Recursion with Memory)
function fibonacciMemo(n: number, memo: Map = new Map()): number {
    if (n <= 1) return n;
    
    // Check if we already calculated this
    if (memo.has(n)) {
        return memo.get(n)!; // Return stored result
    }
    
    // Calculate and store for future use
    const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
    memo.set(n, result);
    return result;
}

// Even better: Bottom-up approach (no recursion needed)
function fibonacciDP(n: number): number {
    if (n <= 1) return n;
    
    const dp = [0, 1]; // Start with base cases
    
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // Build up from smaller problems
    }
    
    return dp[n];
}

// Performance comparison for fib(40):
console.time("Naive");
console.log(fibonacciNaive(40));  // Takes several seconds!
console.timeEnd("Naive");

console.time("Memoized");
console.log(fibonacciMemo(40));   // Instant!
console.timeEnd("Memoized");

console.time("DP");
console.log(fibonacciDP(40));     // Instant!
console.timeEnd("DP");