Recursive Tree Algorithms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

/*
 * THE SUBTREE THINKING TEMPLATE
 * 
 * Replace the comments with your specific logic:
 */
 
function solveTreeProblem(node: TreeNode | null): ResultType {
    // Base case: What's the answer for an empty tree?
    if (node === null) {
        return /* identity/base value */;
    }
    
    // STEP 1: What do I need from the left subtree?
    const leftResult = solveTreeProblem(node.left);
    
    // STEP 2: What do I need from the right subtree?
    const rightResult = solveTreeProblem(node.right);
    
    // STEP 3: How do I combine these with the current node?
    return combineResults(node.value, leftResult, rightResult);
}
 
/*
 * EXAMPLES OF THE FRAMEWORK IN ACTION:
 */
 
// Problem: Sum of all values
// Q: What do I need? The sum of each subtree.
// A: My answer = my value + left sum + right sum
function sum(node: TreeNode<number> | null): number {
    if (node === null) return 0;  // Empty tree sums to 0
    
    const leftSum = sum(node.left);   // Sum of left subtree
    const rightSum = sum(node.right); // Sum of right subtree
    
    return node.value + leftSum + rightSum;  // Combine
}
 
// Problem: Is tree symmetric?
// Q: What do I need? Whether subtrees are mirrors of each other.
// A: Need to compare left's left with right's right, etc.
function isSymmetric(root: TreeNode | null): boolean {
    if (root === null) return true;
    return isMirror(root.left, root.right);
}
 
function isMirror(left: TreeNode | null, right: TreeNode | null): boolean {
    if (left === null && right === null) return true;
    if (left === null || right === null) return false;
    
    // What do I need from subtrees? 
    // That left's subtrees mirror right's subtrees (crossed)
    return left.value === right.value &&
           isMirror(left.left, right.right) &&   // Outer edges
           isMirror(left.right, right.left);     // Inner edges
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

/**
 * PROBLEM: Find the diameter of a binary tree.
 * 
 * Diameter = the length of the longest path between any two nodes.
 * The path may or may not pass through the root.
 * 
 * SUBTREE THINKING:
 * Q: What do I need from each subtree?
 * A: Two things:
 *    1. The height of the subtree (to compute paths through this node)
 *    2. The diameter within the subtree (in case the longest path
 *       doesn't go through this node)
 * 
 * Q: How do I combine?
 * A: The diameter at this node is the max of:
 *    - Path through this node: left_height + right_height + 2
 *    - Diameter entirely in left subtree
 *    - Diameter entirely in right subtree
 */
 
interface DiameterResult {
    height: number;    // Height of this subtree
    diameter: number;  // Best diameter found in this subtree
}
 
function diameterHelper(node: TreeNode | null): DiameterResult {
    // Base case: empty tree
    if (node === null) {
        return { height: -1, diameter: 0 };
    }
    
    // Get info from subtrees
    const left = diameterHelper(node.left);
    const right = diameterHelper(node.right);
    
    // Compute height at this node
    const height = 1 + Math.max(left.height, right.height);
    
    // Compute diameter:
    // - Path through this node: left_height + right_height + 2 edges
    //   (we add 2 because we need edges from left child to this node,
    //    and from this node to right child)
    const pathThroughNode = left.height + right.height + 2;
    
    // Best diameter is max of: path through here, or best in children
    const diameter = Math.max(pathThroughNode, left.diameter, right.diameter);
    
    return { height, diameter };
}
 
function diameter(root: TreeNode | null): number {
    return diameterHelper(root).diameter;
}
 
/**
 * PROBLEM: Check if tree is a valid BST.
 * 
 * SUBTREE THINKING:
 * Q: What do I need from each subtree?
 * A: Three things:
 *    1. Is the subtree a valid BST?
 *    2. The minimum value in the subtree
 *    3. The maximum value in the subtree
 * 
 * Q: How do I combine?
 * A: This tree is a valid BST if:
 *    - Left subtree is valid BST
 *    - Right subtree is valid BST
 *    - Left max < this value < Right min
 */
 
interface BSTResult {
    isValid: boolean;
    min: number;
    max: number;
}
 
function validateBSTHelper(node: TreeNode<number> | null): BSTResult {
    // Base case: empty tree is a valid BST with no range
    if (node === null) {
        return { isValid: true, min: Infinity, max: -Infinity };
    }
    
    // Get info from subtrees
    const left = validateBSTHelper(node.left);
    const right = validateBSTHelper(node.right);
    
    // Combine: check all BST conditions
    const isValid = left.isValid && 
                    right.isValid && 
                    left.max < node.value && 
                    node.value < right.min;
    
    // Compute min/max for this subtree
    const min = Math.min(node.value, left.min, right.min);
    const max = Math.max(node.value, left.max, right.max);
    
    return { isValid, min, max };
}
 
function isValidBST(root: TreeNode<number> | null): boolean {
    return validateBSTHelper(root).isValid;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

/**
 * PROBLEM: Find all root-to-leaf paths that sum to a target.
 * 
 * SUBTREE THINKING:
 * Q: What do I pass DOWN to subtrees?
 * A: The remaining sum needed (target - path sum so far)
 *    and the current path for collecting results.
 * 
 * Q: What do I get BACK from subtrees?
 * A: All valid paths in that subtree (collected in result).
 */
 
function pathSum(
    root: TreeNode<number> | null, 
    targetSum: number
): number[][] {
    const result: number[][] = [];
    pathSumHelper(root, targetSum, [], result);
    return result;
}
 
function pathSumHelper(
    node: TreeNode<number> | null,
    remaining: number,      // Passed DOWN: sum still needed
    currentPath: number[],  // Passed DOWN: path so far
    result: number[][]      // Accumulated: collect all valid paths
): void {
    if (node === null) return;
    
    // Add current node to path
    currentPath.push(node.value);
    
    // Check if this is a leaf with the right sum
    if (node.left === null && node.right === null) {
        if (remaining === node.value) {
            result.push([...currentPath]);  // Found a valid path!
        }
    } else {
        // Pass updated remaining sum DOWN to subtrees
        pathSumHelper(node.left, remaining - node.value, currentPath, result);
        pathSumHelper(node.right, remaining - node.value, currentPath, result);
    }
    
    // Backtrack: remove current node when returning up
    currentPath.pop();
}
 
/**
 * PROBLEM: BST Validation with bounds passed down.
 * 
 * SUBTREE THINKING:
 * Q: What do I pass DOWN?
 * A: The valid range (min, max) for this subtree's values.
 * 
 * As we go LEFT: the max bound tightens (must be < parent)
 * As we go RIGHT: the min bound tightens (must be > parent)
 */
 
function isValidBSTBounds(
    node: TreeNode<number> | null,
    min: number = -Infinity,  // Passed DOWN: lower bound
    max: number = Infinity    // Passed DOWN: upper bound
): boolean {
    if (node === null) return true;
    
    // Check if current node violates the bounds
    if (node.value <= min || node.value >= max) {
        return false;
    }
    
    // Recurse with tightened bounds
    // Left child: all values must be less than current node
    // Right child: all values must be greater than current node
    return isValidBSTBounds(node.left, min, node.value) &&
           isValidBSTBounds(node.right, node.value, max);
}
 
/**
 * PROBLEM: Print all ancestors of a given node.
 * 
 * SUBTREE THINKING:
 * Q: What do I pass DOWN? The current path from root.
 * Q: When do I print? When I find the target node.
 */
 
function printAncestors(
    node: TreeNode<number> | null,
    target: number,
    ancestors: number[] = []  // Passed DOWN: path from root
): boolean {
    if (node === null) return false;
    
    // Check if this is the target
    if (node.value === target) {
        console.log("Ancestors:", ancestors);
        return true;
    }
    
    // Add current node to ancestors and search children
    ancestors.push(node.value);
    const found = printAncestors(node.left, target, ancestors) ||
                  printAncestors(node.right, target, ancestors);
    ancestors.pop();  // Backtrack
    
    return found;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

/**
 * PROBLEM: Find the Lowest Common Ancestor (LCA) of two nodes.
 * 
 * SUBTREE THINKING:
 * The LCA is the deepest node that has both targets in its subtree.
 * 
 * Q: What do I need from subtrees?
 * A: Whether each target is found in that subtree.
 *    If target1 is in left and target2 is in right, current node is LCA.
 *    If both are in same subtree, LCA is deeper in that subtree.
 * 
 * INDEPENDENCE: We search left and right independently.
 *               If found in left, we know it's NOT in right.
 */
 
function lowestCommonAncestor(
    root: TreeNode | null,
    p: TreeNode,
    q: TreeNode
): TreeNode | null {
    // Base case: empty tree or target found
    if (root === null || root === p || root === q) {
        return root;
    }
    
    // Search in subtrees INDEPENDENTLY
    const leftResult = lowestCommonAncestor(root.left, p, q);
    const rightResult = lowestCommonAncestor(root.right, p, q);
    
    // Combine: determine LCA based on where targets were found
    if (leftResult !== null && rightResult !== null) {
        // One target in each subtree → this node is LCA
        return root;
    }
    
    // Both in same subtree (or not found)
    return leftResult !== null ? leftResult : rightResult;
}
 
/**
 * PROBLEM: Maximum path sum in binary tree.
 * Path can start and end at any node, but must be connected.
 * 
 * SUBTREE THINKING:
 * For each node, we consider paths that:
 * 1. Go through this node (left path + node + right path)
 * 2. Are entirely in left subtree
 * 3. Are entirely in right subtree
 * 
 * Q: What do I need from subtrees?
 * A: The maximum sum of a path that STARTS at the subtree root
 *    (so I can extend it through the current node)
 * 
 * INDEPENDENCE: Each subtree's best path is computed separately.
 */
 
function maxPathSum(root: TreeNode<number> | null): number {
    let maxSum = -Infinity;
    
    function maxGain(node: TreeNode<number> | null): number {
        if (node === null) return 0;
        
        // Get max path starting from each child (or 0 if negative)
        const leftGain = Math.max(maxGain(node.left), 0);
        const rightGain = Math.max(maxGain(node.right), 0);
        
        // Path through current node (potential new maximum)
        const pathThroughNode = node.value + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathThroughNode);
        
        // Return max path that can be extended by parent
        // (can only use one child, not both)
        return node.value + Math.max(leftGain, rightGain);
    }
    
    maxGain(root);
    return maxSum;
}
 
/**
 * PROBLEM: Given a binary tree, calculate the total tilt.
 * Tilt of a node = |sum of left subtree - sum of right subtree|
 * Total tilt = sum of all node tilts.
 * 
 * SUBTREE THINKING:
 * Q: What do I need from subtrees?
 * A: The sum of all values in that subtree.
 *    With that, I can compute tilt = |leftSum - rightSum|
 * 
 * Q: What do I return?
 * A: The sum of this subtree (for parent's tilt calculation)
 * 
 * We accumulate total tilt in a closure variable.
 */
 
function findTilt(root: TreeNode<number> | null): number {
    let totalTilt = 0;
    
    function subtreeSum(node: TreeNode<number> | null): number {
        if (node === null) return 0;
        
        const leftSum = subtreeSum(node.left);
        const rightSum = subtreeSum(node.right);
        
        // Compute and accumulate tilt at this node
        totalTilt += Math.abs(leftSum - rightSum);
        
        // Return sum for parent's calculation
        return node.value + leftSum + rightSum;
    }
    
    subtreeSum(root);
    return totalTilt;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

// ❌ WRONG: Forgetting to backtrack
function printPathsWrong(node: TreeNode | null, path: number[]): void {
    if (node === null) return;
    path.push(node.value);
    if (node.left === null && node.right === null) {
        console.log(path);  // Path includes nodes from other branches!
    }
    printPathsWrong(node.left, path);
    printPathsWrong(node.right, path);
    // Missing: path.pop();  ← BUG!
}
 
// ✅ CORRECT: Always backtrack
function printPathsCorrect(node: TreeNode | null, path: number[]): void {
    if (node === null) return;
    path.push(node.value);
    if (node.left === null && node.right === null) {
        console.log(path);
    }
    printPathsCorrect(node.left, path);
    printPathsCorrect(node.right, path);
    path.pop();  // Backtrack!
}
 
// ❌ WRONG: Computing height multiple times
function isBalancedSlow(node: TreeNode | null): boolean {
    if (node === null) return true;
    // height() is O(n), called for every node = O(n²) total!
    return Math.abs(height(node.left) - height(node.right)) <= 1 &&
           isBalancedSlow(node.left) &&
           isBalancedSlow(node.right);
}
 
// ✅ CORRECT: Compute height once, return both values
function isBalancedFast(node: TreeNode | null): boolean {
    function helper(node: TreeNode | null): { height: number; balanced: boolean } {
        if (node === null) return { height: -1, balanced: true };
        
        const left = helper(node.left);
        const right = helper(node.right);
        
        return {
            height: 1 + Math.max(left.height, right.height),
            balanced: left.balanced && right.balanced && 
                      Math.abs(left.height - right.height) <= 1
        };
    }
    return helper(node).balanced;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/**
 * PATTERN: Global state via closure
 * 
 * Use when you need to track something across all nodes
 * that doesn't fit naturally as a return value.
 */
 
// Example: Find k-th smallest element in BST
function kthSmallest(root: TreeNode<number> | null, k: number): number {
    // Closure state
    let count = 0;
    let result = -1;
    
    function inorder(node: TreeNode<number> | null): void {
        if (node === null || count >= k) return;  // Early exit
        
        inorder(node.left);
        
        count++;
        if (count === k) {
            result = node.value;
            return;  // Found it!
        }
        
        inorder(node.right);
    }
    
    inorder(root);
    return result;
}
 
// Example: Count nodes in range [low, high] in BST
function countNodesInRange(
    root: TreeNode<number> | null, 
    low: number, 
    high: number
): number {
    let count = 0;  // Closure state
    
    function traverse(node: TreeNode<number> | null): void {
        if (node === null) return;
        
        // Optimization: prune search using BST property
        if (node.value > low) {
            traverse(node.left);
        }
        
        if (node.value >= low && node.value <= high) {
            count++;
        }
        
        if (node.value < high) {
            traverse(node.right);
        }
    }
    
    traverse(root);
    return count;
}
 
// Example: Collect all values at a specific depth
function valuesAtDepth(root: TreeNode<number> | null, targetDepth: number): number[] {
    const values: number[] = [];  // Closure state
    
    function traverse(node: TreeNode<number> | null, depth: number): void {
        if (node === null) return;
        
        if (depth === targetDepth) {
            values.push(node.value);
            return;  // Don't go deeper
        }
        
        traverse(node.left, depth + 1);
        traverse(node.right, depth + 1);
    }
    
    traverse(root, 0);
    return values;
}