Recursive Tree Algorithms - Learning Module

Loading content...

0/276

Thinking with Subtrees

The Subtree Mindset

Throughout this module, we've built up to a powerful idea: every tree is a composition of subtrees, and every subtree is itself a complete tree. This final page elevates that idea into a systematic problem-solving approach.

Thinking with subtrees means approaching every tree problem by asking:

"If I had the answer for the left subtree and the answer for the right subtree, how would I combine them to get the answer for the whole tree?"

This single question unlocks solutions to an enormous range of tree problems. It's the recursive mindset crystallized into a practical technique.

By the end of this page, you'll have internalized this approach so deeply that tree problems will feel fundamentally different—simpler, more structured, and more approachable.

What You Will Learn

By the end of this page, you will master the subtree thinking paradigm, understand how to decompose complex tree problems into subtree subproblems, learn advanced patterns for passing information between subtrees, and build confidence in solving novel tree problems through systematic decomposition.

The Core Question: What Do I Need From My Subtrees?

When faced with any tree problem, train yourself to ask this question first:

"What information do I need from my left and right subtrees to solve the problem at this node?"

This question forces you to think recursively. You're not trying to solve the whole problem at once—you're identifying the subproblem structure.

The Three-Part Framework:

What do I need from the left subtree? (What should the recursive call return?)
What do I need from the right subtree? (Same question, right side)
How do I combine these with the current node to produce my answer?

Once you answer these questions, the algorithm writes itself.

Subtree Thinking Framework
TypeScript
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
}

The Leap of Faith

Don't try to trace through the entire recursion. Trust that your recursive calls return the correct answer for subtrees. Focus only on: (1) is my base case correct? (2) if I had correct subtree answers, is my combination correct? If both are yes, the algorithm is correct.

Returning Complex Information from Subtrees

Sometimes a single value isn't enough. Complex tree problems often require subtrees to return multiple pieces of information. This is where the subtree thinking approach shows its true power.

Technique: Return Tuples or Objects

When you need multiple values from a subtree, return them together. This avoids:

Multiple traversals (inefficient)
Global variables (error-prone)
Complex state management (hard to reason about)

Returning Multiple Values
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;
}

Single Pass Efficiency

By returning multiple values, we compute everything in a single O(n) traversal. Without this technique, you might need separate traversals for height and diameter, resulting in O(n²) time. The tuple/object return pattern is essential for efficient tree algorithms.

Passing Information Down to Subtrees

Not all information flows up from subtrees. Sometimes you need to pass information down to subtrees. This is the Accumulate Pattern we introduced earlier, but now we'll explore it in depth.

When to Pass Information Down:

Computing depth (distance from root)
Path sums (sum of values from root to current node)
Validation with bounds (BST validation with min/max constraints)
Tracking paths (recording the path from root to target)
Conditional logic based on ancestors

Passing Information Down
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;
}

Backtracking Is Essential

When passing mutable state (like a path list) down the tree, you MUST backtrack when returning. After processing children, remove what you added. Otherwise, the path will contain incorrect nodes from other branches.

The Subtree Independence Principle in Action

We established earlier that subtrees are independent—they share no nodes. This independence enables powerful algorithmic techniques:

1. Parallel Processing: Subtrees can be processed concurrently without synchronization.

2. Divide and Conquer: Each subtree is an independent subproblem.

3. Clean Composition: Combine subtree results without worrying about interference.

4. Independent Failures: If one subtree fails a condition, it doesn't affect the other.

Let's see this principle applied to a sophisticated problem:

Subtree Independence Examples
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;
}

Common Pitfalls in Subtree Thinking

Even with the subtree mindset, there are common mistakes to watch for:

Pitfalls and How to Avoid Them

•Wrong base case value — The base case must be the identity for your combining operation. Sum uses 0, product uses 1, max uses -∞, min uses +∞, AND uses true, OR uses false.
•Forgetting to backtrack — When passing mutable state down (lists, paths), always undo changes when returning. Use path.pop() or similar after recursive calls.
•Computing the same thing twice — If you need height AND diameter, compute both in one pass using tuple returns. Don't traverse the tree multiple times.
•Not trusting the recursion — Avoid trying to trace the full recursion mentally. Trust that recursive calls return correct values; focus on base case and combination.
•Confusing height and depth — Height looks DOWN (combine pattern, compute from leaves up). Depth looks UP (accumulate pattern, pass from root down).
•Modifying the tree unintentionally — If you need the original tree later, don't mutate it. Either work on a copy or use non-destructive operations.
•Ignoring the empty subtree — A node with one child still has an empty subtree on the other side. Your base case must handle this correctly.

Common Mistakes
TypeScript
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;
}

Advanced Pattern: Global State with Closures

Some problems require tracking a global maximum, minimum, or count across all nodes. While pure recursion passes information only through parameters and return values, closures offer an elegant alternative.

The Pattern:

Define a variable in the outer scope (captured by closure)
The recursive function updates this variable as it traverses
Return the captured value after traversal completes

This avoids passing accumulators through every recursive call while maintaining clean code.

Closure Pattern
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;
}

When to Use Closures vs Return Values

Use return values when the result naturally flows up (height, size, sum). Use closures when you're tracking something global that doesn't compose naturally (k-th element, global maximum, collecting specific nodes). If in doubt, try return values first—they're more testable and reusable.

Practice: Apply Subtree Thinking

To solidify your understanding, work through these problems using the subtree thinking approach. For each, explicitly answer:

What do I need from my subtrees?
What is my base case?
How do I combine results?

Practice Problems with Hints
Problem	Difficulty	Key Insight
Count nodes with exactly one child	Easy	Combine pattern: count in subtrees + check current node
Find maximum width of tree (max nodes at any level)	Medium	BFS approach or track level info passed down
Flatten binary tree to linked list (in-place)	Medium	Transform pattern: flatten children, then reconnect
Serialize and deserialize binary tree	Medium	Preorder traversal with null markers; rebuild recursively
Check if tree is subtree of another	Medium	Search for matching root, then check structural equality
Construct tree from inorder + preorder traversals	Hard	Divide and conquer using root position in inorder
Binary tree maximum path sum	Hard	Return extendable path, track global max separately
Count complete tree nodes in O(log² n)	Hard	Use tree properties to avoid full traversal

Approach Each Problem Systematically

Before coding, write down the three answers above. This forces you to design the algorithm before implementing. The code often becomes trivial once you've answered these questions clearly.

Summary: Mastering Recursive Tree Algorithms

This module has taken you from understanding why trees and recursion are natural partners to mastering sophisticated recursive tree algorithms. Let's consolidate everything:

Module Mastery Checklist

•Trees are recursively defined — Every tree is either empty or a node with subtrees. Algorithms mirror this definition.
•Subtrees are complete, independent trees — Each subtree can be processed by the same algorithm as the whole tree.
•Four fundamental patterns — Combine (bottom-up), Accumulate (top-down), Search (find nodes), Transform (build new trees).
•Complex returns for complex problems — Return tuples/objects when you need multiple values from subtrees.
•Pass information down when needed — Depth, bounds, paths, and constraints flow from ancestors to descendants.
•Backtrack with mutable state — When passing lists or paths down, always undo changes when returning up.
•Closures for global tracking — Track global maxima, counts, or collections without threading through parameters.
•Trust the recursion — Focus on base case and combination; don't trace the full execution.

The Subtree Thinking Mantra:

"If I had the answers for my subtrees, how would I compute the answer for this tree?"

This question, applied systematically, unlocks solutions to virtually any tree problem. You now have the conceptual framework and practical techniques to approach tree problems with confidence.

Module Complete: Recursive Tree Algorithms

You've mastered the art of recursive tree thinking. This isn't just a technique—it's a fundamental way of understanding hierarchical structures. Every tree problem you encounter from now on can be approached with this framework. Practice the patterns, trust the recursion, and tree problems will transform from challenges into opportunities to apply elegant solutions.