Path Sum Problems - Common Tree Patterns & Problem Types | OneNoughtOne

0/361

Data Structures & AlgorithmsCommon Tree Patterns & Problem Types

Common Tree Patterns & Problem Types

LevelIntermediate

Duration120 mins

TopicCommon Tree Patterns & Problem Types

1 / 5

Path Sum Problems

Sum Along the Path — The Foundation of Tree Computation

Imagine you're a delivery driver navigating a tree-shaped network of roads. Each road segment has a toll fee, and your company reimburses you exactly $100 for each complete route from headquarters (the root) to a delivery point (a leaf). Your goal: find all delivery routes where the total toll equals exactly your reimbursement.

This intuitive scenario perfectly captures path sum problems — one of the most elegant and frequently tested patterns in tree algorithms. These problems ask us to accumulate values along paths through a tree, testing conditions, finding optima, or enumerating possibilities.

Path sum problems form the backbone of tree-based computation because they force us to grapple with the fundamental nature of trees: hierarchical accumulation. Every node builds upon the context of its ancestors, and solutions must propagate both downward and upward through the structure.

What You Will Master

By the end of this page, you will:

• Understand the taxonomy of path sum problems (root-to-leaf, root-to-any, any-to-any) • Master recursive accumulation patterns with proper base case design • Apply prefix sum optimization for O(n) path counting in any-path scenarios • Implement backtracking for enumerating all valid paths • Recognize path sum disguises in real-world problems (network costs, decision trees, probability paths)

Understanding Path Sum Problems

A path sum problem asks whether we can find a path through a tree where the sum of node values satisfies some condition. The variations depend on three key dimensions:

1. Path Definition: Where must the path start and end?

Root-to-leaf: Start at root, end at a leaf (node with no children)
Root-to-any: Start at root, end at any node
Any-to-any: Start and end at any nodes (with some directional constraint)

2. Query Type: What question are we answering?

Existence: Does such a path exist?
Count: How many such paths exist?
Enumeration: List all such paths
Maximum/Minimum: Find the path with optimal sum

3. Directionality: How can we traverse?

Downward only: Only from parent to child
Upward only: Only from child to parent (rare)
Any direction: Can traverse in any direction along edges

Path Sum Problem Taxonomy
Path Type	Classic Problem	Key Insight	Complexity
Root-to-leaf, existence	Path Sum I	Simple recursion with sum propagation	O(n)
Root-to-leaf, enumeration	Path Sum II	Backtracking with path reconstruction	O(n²) worst case
Root-to-any, count	Path Sum III	Prefix sum with hash map	O(n)
Any-to-any, maximum	Maximum Path Sum	DFS with split-path handling	O(n)
Root-to-leaf, all sums	Sum Root to Leaf Numbers	Accumulate digit strings	O(n)

The Core Insight

Every path sum problem shares a fundamental structure: as you traverse from node to node, you're building a running total. The variations differ in where the path can start, where it must end, and what you do with the accumulated sum. Once you see this pattern, variations become straightforward modifications of a core algorithm.

Root-to-Leaf Path Sum — The Fundamental Pattern

The canonical path sum problem asks: Given a binary tree and a target sum, determine if the tree has a root-to-leaf path such that adding up all node values along the path equals the given sum.

This is the most natural form of the problem because it aligns with how we typically think about tree traversal — starting at the root and working downward to the leaves.

The Recursive Insight:

At each node, we face a simple decision: the current node contributes its value to the running sum. We then check if either child can complete the path with the remaining sum.

The recursive structure is elegant:

Base case: At a leaf, check if the remaining target equals the leaf's value
Recursive case: Subtract current value from target, recurse on children

Why this works:

The key insight is that we transform the problem as we descend. Instead of asking "does any path from root to leaf sum to T?", we ask at each node: "does any path from this node to a leaf sum to (T - running_sum)?"

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
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Determines if there exists a root-to-leaf path with the given sum.
 * 
 * Key insights:
 * 1. We propagate (target - current_value) down the tree
 * 2. At a leaf, we check if remaining target equals leaf value
 * 3. An empty tree cannot have any path, so null returns false
 * 
 * Time: O(n) - visit each node once
 * Space: O(h) - recursion stack depth where h is tree height
 */
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    // Empty tree has no paths
    if (root === null) {
        return false;
    }
    
    // Leaf node check: does this complete a valid path?
    // A leaf is a node with NO children (both left and right are null)
    if (root.left === null && root.right === null) {
        return root.val === targetSum;
    }
    
    // Recursive case: can either subtree complete the path?
    // We subtract current node's value from target for child search
    const remainingSum = targetSum - root.val;
    
    return hasPathSum(root.left, remainingSum) || 
           hasPathSum(root.right, remainingSum);
}

Critical Edge Case: What is a Leaf?

A common bug is misidentifying leaves. A leaf is a node with ZERO children, not a null node. If you check (root === null && targetSum === 0), you'll incorrectly return true for internal nodes with one child. Always verify both children are null before treating a node as a leaf.

Visualizing the Algorithm:

Consider this tree with target sum = 22:

        5
       / 
      4   8
     /   / 
    11  13  4
   /  \      
  7    2      1

Path trace for 5 → 4 → 11 → 2:

At 5: target = 22, remaining = 22 - 5 = 17
At 4: target = 17, remaining = 17 - 4 = 13
At 11: target = 13, remaining = 13 - 11 = 2
At 2: target = 2, is leaf? Yes! 2 === 2 ✓

This path sums to 5 + 4 + 11 + 2 = 22. We found a valid path.

Path trace for 5 → 8 → 13:

At 5: target = 22, remaining = 17
At 8: target = 17, remaining = 9
At 13: target = 9, is leaf? Yes! 13 !== 9 ✗

This path sums to 5 + 8 + 13 = 26 ≠ 22. Not valid.

Path Enumeration with Backtracking

When we need to find all paths that satisfy a sum condition, we move from existence checking to enumeration. This requires a fundamentally different approach: we must not only find paths but also remember them.

The key technique is backtracking — we build a path as we descend, record it when we find a solution, and then undo our choice as we return from recursion. This "try, record, and undo" pattern is central to many combinatorial algorithms.

Why backtracking is necessary:

Unlike the simple existence check where we only need to return true/false, enumeration requires maintaining state (the current path). As we explore different branches, we must:

Add the current node to the path when entering
Record the path if we've found a valid solution
Remove the current node when leaving (backtracking)

This ensures that each recursive call sees the path representing only its ancestors.

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
/**
 * Finds all root-to-leaf paths where the path sum equals targetSum.
 * 
 * This uses backtracking: we maintain a current path, explore branches,
 * and "undo" our choice when returning from recursion.
 * 
 * Time: O(n²) worst case - we visit n nodes, and copying paths can take O(n)
 * Space: O(h) recursion + O(n) for current path + O(n * h) for result storage
 */
function pathSum(root: TreeNode | null, targetSum: number): number[][] {
    const result: number[][] = [];
    const currentPath: number[] = [];
    
    function dfs(node: TreeNode | null, remainingSum: number): void {
        if (node === null) {
            return;
        }
        
        // Add current node to the path (make our choice)
        currentPath.push(node.val);
        
        // Check if we've reached a leaf with the exact sum
        if (node.left === null && node.right === null) {
            if (node.val === remainingSum) {
                // Found a valid path! Make a copy to store
                // We must copy because currentPath will be modified later
                result.push([...currentPath]);
            }
        } else {
            // Not a leaf, continue exploring
            const newRemaining = remainingSum - node.val;
            dfs(node.left, newRemaining);
            dfs(node.right, newRemaining);
        }
        
        // CRITICAL: Remove current node from path (backtrack)
        // This "undoes" our choice so parent sees correct state
        currentPath.pop();
    }
    
    dfs(root, targetSum);
    return result;
}

The Backtracking Pattern

Backtracking always follows this template:

Choose: Add the current element to your working state
Explore: Recursively explore with this choice
Unchoose: Remove the element (restore previous state)

This pattern works for path problems, permutations, combinations, N-Queens, Sudoku, and countless other problems. Master it once, apply it everywhere.

Understanding the Copy Requirement:

Notice that we store [...currentPath] (a copy), not currentPath directly. This is crucial! If we stored the reference, we'd end up with all result entries pointing to the same array, which gets modified and eventually emptied.

Complexity Analysis:

Time: We visit each node once (O(n)), but when we find a valid path, we copy it which takes O(path_length). In a balanced tree, paths are O(log n), giving O(n log n). In a skewed tree, paths are O(n), and if all paths are valid, we have O(n) copies of O(n) paths = O(n²).
Space: The recursion stack is O(h) where h is tree height. The current path is also O(h). The result storage depends on how many valid paths exist.

The elegance of backtracking:

Backtracking elegantly handles the exponential nature of enumeration problems. There might be exponentially many paths to explore, but we share the computation of common prefixes. We don't re-traverse from the root for each path; we incrementally extend and retract a single path.

Any-to-Any Paths with Prefix Sums

The most challenging path sum variant is Path Sum III: count all paths that sum to a target, where paths can start and end at any nodes (but must go downward from ancestor to descendant).

This is fundamentally harder because we can't simply track one running sum. A path from node A to node B might be: root → ... → A → ... → B, where only the A→B portion counts.

The Naive Approach:

For each node, consider it as a potential path start and check all downward paths from there. This gives O(n²) or even O(n³) solutions.

The Prefix Sum Insight:

Here's the breakthrough: if we know the sum from root to any node X, we can compute the sum of any path from A to X as:

sum(A to X) = sum(root to X) - sum(root to A)

So to find paths summing to target from any ancestor A to X:

sum(root to X) - sum(root to A) = target sum(root to A) = sum(root to X) - target

If we track all prefix sums (root to each ancestor) in a hash map, we can count valid path starts in O(1)!

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
/**
 * Counts paths that sum to target, where paths can start/end at any nodes
 * but must go downward (parent to child direction only).
 * 
 * Key insight: Use prefix sums. If prefixSum at current node is S,
 * and we've seen a prefix sum of (S - target) at some ancestor,
 * then the path from that ancestor to here sums to target.
 * 
 * Time: O(n) - single traversal with O(1) hash operations
 * Space: O(h) - recursion stack + hash map entries for current path
 */
function pathSumIII(root: TreeNode | null, targetSum: number): number {
    // Map: prefix_sum -> count of ancestors with this prefix sum
    const prefixSumCount = new Map<number, number>();
    
    // Initialize with 0 sum (handles paths starting at root)
    // A prefix sum of 0 exists "before" the root
    prefixSumCount.set(0, 1);
    
    function dfs(node: TreeNode | null, currentSum: number): number {
        if (node === null) {
            return 0;
        }
        
        // Update current prefix sum (root to this node)
        currentSum += node.val;
        
        // Count paths ending here: we need ancestors with sum = currentSum - target
        // If such an ancestor exists, path from it to here sums to target
        const targetPrefixSum = currentSum - targetSum;
        let pathCount = prefixSumCount.get(targetPrefixSum) || 0;
        
        // Add current prefix sum to the map for descendants to use
        prefixSumCount.set(currentSum, (prefixSumCount.get(currentSum) || 0) + 1);
        
        // Explore children
        pathCount += dfs(node.left, currentSum);
        pathCount += dfs(node.right, currentSum);
        
        // CRITICAL: Backtrack! Remove current sum from map
        // This ensures siblings don't see our prefix sum
        const countAfterRemoval = prefixSumCount.get(currentSum)! - 1;
        if (countAfterRemoval === 0) {
            prefixSumCount.delete(currentSum);
        } else {
            prefixSumCount.set(currentSum, countAfterRemoval);
        }
        
        return pathCount;
    }
    
    return dfs(root, 0);
}

Why Initialize with prefixSumCount[0] = 1?

The initial entry (0, 1) handles paths that start at the root. If currentSum === targetSum at some node, we need to count the path from root to here. That path's 'start prefix sum' is 0 (before the root), so we need to find prefixSumCount[currentSum - targetSum] = prefixSumCount[0] = 1.

Visualizing the Algorithm:

Consider this tree with targetSum = 8:

Tracing the path 10 → 5 → 3:

At 10: currentSum = 10, looking for 10 - 8 = 2 (not found), add {10: 1}
At 5: currentSum = 15, looking for 15 - 8 = 7 (not found), add {15: 1}
At 3: currentSum = 18, looking for 18 - 8 = 10 (found! count = 1)
- This finds the path 5 → 3 (actually need to check: 18 - 10 = 8 ✓)

Another path: 10 → 5 → 2 → 1:

At 10: currentSum = 10
At 5: currentSum = 15
At 2: currentSum = 17, looking for 17 - 8 = 9 (not found)
At 1: currentSum = 18, looking for 18 - 8 = 10 (found!)
- This finds the path 5 → 2 → 1 (5 + 2 + 1 = 8 ✓)

The backtracking is essential:

When we finish exploring the left subtree of node 5 and move to the right subtree, we must remove the prefix sums from the left subtree. Otherwise, the right subtree might incorrectly "see" prefix sums from unrelated paths.

Maximum Path Sum — The Ultimate Challenge

The hardest path sum variant is Binary Tree Maximum Path Sum: find the maximum sum among all paths, where a path can start and end at any nodes (no directionality constraint beyond connectivity).

This problem is challenging because:

Paths aren't constrained to root-to-leaf or downward-only
A path might go through a node as a "peak" (up from one child, through node, down to other child)
Node values can be negative, complicating greedy decisions

The Key Insight: Contribution vs. Through-Path

At each node, we must distinguish two concepts:

Max contribution up: The maximum sum this node can contribute to a path that continues upward to its parent. This can only include one subtree (or neither), since paths can't fork.
Max through-path: The maximum sum of a path that "peaks" at this node — coming up from left child, through this node, and down to right child. This path is complete and won't extend further.

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
/**
 * Finds the maximum path sum where path can start and end at any nodes.
 * 
 * Key insight: At each node, we track two things:
 * 1. maxGain: max sum this subtree can contribute to parent (single branch)
 * 2. globalMax: max complete path seen so far (might peak at any node)
 * 
 * Time: O(n) - single traversal
 * Space: O(h) - recursion stack
 */
function maxPathSum(root: TreeNode | null): number {
    // Use object to allow mutation in closure (alternative: class field)
    let globalMax = -Infinity;
    
    /**
     * Returns the maximum "gain" this node can contribute to a path
     * that continues upward to its parent.
     * 
     * Side effect: updates globalMax if a better complete path is found
     */
    function maxGain(node: TreeNode | null): number {
        if (node === null) {
            return 0;
        }
        
        // Recursively get max gain from left and right subtrees
        // Use Math.max with 0: negative contributions are "free" to ignore
        // (It's always better to not take a negative-sum path)
        const leftGain = Math.max(0, maxGain(node.left));
        const rightGain = Math.max(0, maxGain(node.right));
        
        // Consider a path that "peaks" at this node:
        // left subtree → this node → right subtree
        // This is a complete path; check if it's the best so far
        const pathThroughNode = node.val + leftGain + rightGain;
        globalMax = Math.max(globalMax, pathThroughNode);
        
        // Return max contribution to parent's path
        // We can only extend in ONE direction (left OR right, not both)
        // because a path can't fork
        return node.val + Math.max(leftGain, rightGain);
    }
    
    maxGain(root);
    return globalMax;
}

The 'Max with Zero' Trick

The line Math.max(0, maxGain(node.left)) is crucial. A negative-sum subtree should contribute 0 (don't include it) rather than hurt our path. This elegant trick handles negative values without complex conditional logic. It's equivalent to saying: 'include this branch only if it helps.'

Why we check globalMax at every node:

The maximum path might peak at any node in the tree — not necessarily the root. So we check at each node: "What if the best path goes left-child → this node → right-child?"

Why maxGain returns only one branch:

When contributing to a parent's path, we can only extend in one direction. Consider:

If we're at node 2, we can contribute to node 1's path by:

Taking the path 3 → 2 → 1 (gain = 3 + 2 = 5)
Or taking the path 4 → 2 → 1 (gain = 4 + 2 = 6)

We can't take 3 → 2 → 4 → ... → 1 because that would require forking at node 2, which isn't a valid path.

Complexity:

Time: O(n) — We visit each node exactly once
Space: O(h) — Recursion stack, where h is tree height (O(log n) to O(n))

Digital Root Problems — A Path Sum Disguise

A fascinating variant is Sum Root to Leaf Numbers: each root-to-leaf path represents a number formed by concatenating node values (like 1→2→3 = 123). Find the total of all such numbers.

This isn't obviously a "sum" problem, but it's structurally identical — we're accumulating information along paths and aggregating at leaves.

The Mathematical Insight:

As we traverse, each digit shifts left (multiply by 10) and adds the new digit:

At root 1: number = 1
At child 2: number = 1 × 10 + 2 = 12
At grandchild 3: number = 12 × 10 + 3 = 123

This is just a different "accumulation function" — instead of adding, we're doing prev * 10 + current.

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
/**
 * Each root-to-leaf path forms a number. Return sum of all such numbers.
 * Example: Paths 1->2->3 and 1->2->4 give 123 + 124 = 247
 * 
 * Key insight: Same structure as path sum, but accumulate with x*10 + digit
 * 
 * Time: O(n)
 * Space: O(h) recursion stack
 */
function sumNumbers(root: TreeNode | null): number {
    function dfs(node: TreeNode | null, currentNumber: number): number {
        if (node === null) {
            return 0;
        }
        
        // Shift current number left by one digit, add this node's value
        currentNumber = currentNumber * 10 + node.val;
        
        // If leaf, this path is complete; return its number
        if (node.left === null && node.right === null) {
            return currentNumber;
        }
        
        // Not a leaf: sum the contributions from both subtrees
        return dfs(node.left, currentNumber) + dfs(node.right, currentNumber);
    }
    
    return dfs(root, 0);
}

Pattern Recognition:

This problem illustrates an important meta-skill: recognizing structural similarity despite surface differences. The "digital root" problem looks different from "path sum" but uses the same traversal pattern:

Aspect	Path Sum	Digital Root
Accumulation	sum += node.val	num = num * 10 + node.val
Base case	compare to target	return the number
Aggregation	OR (existence) or list	SUM of all paths

Once you see this structural mapping, you realize that many tree problems are variations on the same theme: propagate context downward, aggregate results upward.

The Generalized Pattern

Many tree problems follow this template:

function solve(node, context):
    if node is null: return base_value
    
    new_context = transform(context, node.val)
    
    if is_leaf(node): return leaf_value(new_context)
    
    return aggregate(
        solve(node.left, new_context),
        solve(node.right, new_context)
    )

Path sum: transform = subtract, aggregate = OR Digital root: transform = *10+, aggregate = SUM Max depth: transform = +1, aggregate = MAX

Real-World Applications

Path sum problems aren't just interview exercises — they model real computational problems across many domains. Understanding these connections helps you recognize where to apply these patterns.

1. Network Cost Optimization:

In a network topology (often tree-shaped for efficiency), path sums represent cumulative latency, bandwidth constraints, or cost. Finding paths within a budget is exactly a path sum problem.

2. Decision Trees in Machine Learning:

Decision trees used for classification accumulate conditions along paths. "Path sum" here is the accumulated probability or the combined constraint set. Pruning decisions often involve path-based computations.

3. Compiler Optimization — Expression Trees:

Arithmetic expressions form trees where path computations help with constant folding, strength reduction, and cost estimation. The "cost" to compute a subexpression flows up the tree.

4. Game Trees and Minimax:

In game AI, values propagate up the tree (minimax). While not strictly "sums," the pattern of propagating and aggregating values along paths is identical.

5. Financial Modeling:

Risk models often use tree structures where path sums represent cumulative exposure. Finding paths exceeding risk thresholds is a path sum search.

Path Sum Patterns in Industry Applications
Application	Tree Structure	Path Sum Represents	Query Type
Network Routing	Router topology	Cumulative latency/hops	Find path ≤ budget
ML Decision Trees	Feature splits	Probability/constraints	Classify by leaf
Compiler AST	Expression tree	Computation cost	Optimize total cost
Version Control	Commit history	Accumulated diffs	Find change paths
File Systems	Directory tree	Cumulative size	Find paths > quota

Transferable Skills

When you master path sum patterns, you're not just preparing for interviews — you're building mental models that directly apply to system design, performance optimization, and architectural decisions. The recursive intuition transfers to any hierarchical domain.

Summary and Key Takeaways

Path sum problems form a foundational pattern in tree algorithms. Let's consolidate what we've learned:

Core Concepts Mastered

•Path types: Root-to-leaf, root-to-any, and any-to-any paths each require different algorithmic approaches
•Recursive propagation: Passing accumulated sums downward transforms the problem at each level
•Backtracking: Essential for path enumeration — add on entry, remove on exit
•Prefix sums: Transform O(n²) any-path counting into O(n) using hash maps
•Contribution vs completion: For max path sum, distinguish between contributing to parent and forming a complete path
•Pattern generalization: Most tree problems share the same structure with different transform and aggregate functions

Key Algorithmic Techniques

For existence/count (root-to-leaf): Simple recursion with sum propagation

For enumeration: Backtracking with path reconstruction

For any-path counting: Prefix sums with hash map

For max path (any direction): Track both contribution up and complete path at each node

What's Next:

Path sum problems taught us to accumulate and aggregate along tree paths. In the next page, we'll explore Lowest Common Ancestor (LCA) problems — where instead of following single paths downward, we must find the meeting point of two paths ascending from different nodes. This seemingly simple problem has profound implications for tree algorithms and forms the basis for many advanced techniques.

Page Complete

You now have a comprehensive understanding of path sum problems — from basic existence checking to optimal prefix-sum solutions to the challenging maximum path sum. These patterns will appear repeatedly in tree problems; recognize them quickly and apply the appropriate technique with confidence.

Data Structures & AlgorithmsCommon Tree Patterns & Problem Types

Common Tree Patterns & Problem Types

LevelIntermediate

Duration120 mins

TopicCommon Tree Patterns & Problem Types

1 / 5

Path Sum Problems

Sum Along the Path — The Foundation of Tree Computation

What You Will Master

By the end of this page, you will:

Understanding Path Sum Problems

A path sum problem asks whether we can find a path through a tree where the sum of node values satisfies some condition. The variations depend on three key dimensions:

1. Path Definition: Where must the path start and end?

Root-to-leaf: Start at root, end at a leaf (node with no children)
Root-to-any: Start at root, end at any node
Any-to-any: Start and end at any nodes (with some directional constraint)

2. Query Type: What question are we answering?

Existence: Does such a path exist?
Count: How many such paths exist?
Enumeration: List all such paths
Maximum/Minimum: Find the path with optimal sum

3. Directionality: How can we traverse?

Downward only: Only from parent to child
Upward only: Only from child to parent (rare)
Any direction: Can traverse in any direction along edges

Path Sum Problem Taxonomy
Path Type	Classic Problem	Key Insight	Complexity
Root-to-leaf, existence	Path Sum I	Simple recursion with sum propagation	O(n)
Root-to-leaf, enumeration	Path Sum II	Backtracking with path reconstruction	O(n²) worst case
Root-to-any, count	Path Sum III	Prefix sum with hash map	O(n)
Any-to-any, maximum	Maximum Path Sum	DFS with split-path handling	O(n)
Root-to-leaf, all sums	Sum Root to Leaf Numbers	Accumulate digit strings	O(n)

The Core Insight

Root-to-Leaf Path Sum — The Fundamental Pattern

The canonical path sum problem asks: Given a binary tree and a target sum, determine if the tree has a root-to-leaf path such that adding up all node values along the path equals the given sum.

This is the most natural form of the problem because it aligns with how we typically think about tree traversal — starting at the root and working downward to the leaves.

The Recursive Insight:

At each node, we face a simple decision: the current node contributes its value to the running sum. We then check if either child can complete the path with the remaining sum.

The recursive structure is elegant:

Base case: At a leaf, check if the remaining target equals the leaf's value
Recursive case: Subtract current value from target, recurse on children

Why this works:

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
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Determines if there exists a root-to-leaf path with the given sum.
 * 
 * Key insights:
 * 1. We propagate (target - current_value) down the tree
 * 2. At a leaf, we check if remaining target equals leaf value
 * 3. An empty tree cannot have any path, so null returns false
 * 
 * Time: O(n) - visit each node once
 * Space: O(h) - recursion stack depth where h is tree height
 */
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    // Empty tree has no paths
    if (root === null) {
        return false;
    }
    
    // Leaf node check: does this complete a valid path?
    // A leaf is a node with NO children (both left and right are null)
    if (root.left === null && root.right === null) {
        return root.val === targetSum;
    }
    
    // Recursive case: can either subtree complete the path?
    // We subtract current node's value from target for child search
    const remainingSum = targetSum - root.val;
    
    return hasPathSum(root.left, remainingSum) || 
           hasPathSum(root.right, remainingSum);
}

Critical Edge Case: What is a Leaf?

Visualizing the Algorithm:

Consider this tree with target sum = 22:

        5
       / 
      4   8
     /   / 
    11  13  4
   /  \      
  7    2      1

Path trace for 5 → 4 → 11 → 2:

At 5: target = 22, remaining = 22 - 5 = 17
At 4: target = 17, remaining = 17 - 4 = 13
At 11: target = 13, remaining = 13 - 11 = 2
At 2: target = 2, is leaf? Yes! 2 === 2 ✓

This path sums to 5 + 4 + 11 + 2 = 22. We found a valid path.

Path trace for 5 → 8 → 13:

At 5: target = 22, remaining = 17
At 8: target = 17, remaining = 9
At 13: target = 9, is leaf? Yes! 13 !== 9 ✗

This path sums to 5 + 8 + 13 = 26 ≠ 22. Not valid.

Path Enumeration with Backtracking

Why backtracking is necessary:

Unlike the simple existence check where we only need to return true/false, enumeration requires maintaining state (the current path). As we explore different branches, we must:

Add the current node to the path when entering
Record the path if we've found a valid solution
Remove the current node when leaving (backtracking)

This ensures that each recursive call sees the path representing only its ancestors.

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
/**
 * Finds all root-to-leaf paths where the path sum equals targetSum.
 * 
 * This uses backtracking: we maintain a current path, explore branches,
 * and "undo" our choice when returning from recursion.
 * 
 * Time: O(n²) worst case - we visit n nodes, and copying paths can take O(n)
 * Space: O(h) recursion + O(n) for current path + O(n * h) for result storage
 */
function pathSum(root: TreeNode | null, targetSum: number): number[][] {
    const result: number[][] = [];
    const currentPath: number[] = [];
    
    function dfs(node: TreeNode | null, remainingSum: number): void {
        if (node === null) {
            return;
        }
        
        // Add current node to the path (make our choice)
        currentPath.push(node.val);
        
        // Check if we've reached a leaf with the exact sum
        if (node.left === null && node.right === null) {
            if (node.val === remainingSum) {
                // Found a valid path! Make a copy to store
                // We must copy because currentPath will be modified later
                result.push([...currentPath]);
            }
        } else {
            // Not a leaf, continue exploring
            const newRemaining = remainingSum - node.val;
            dfs(node.left, newRemaining);
            dfs(node.right, newRemaining);
        }
        
        // CRITICAL: Remove current node from path (backtrack)
        // This "undoes" our choice so parent sees correct state
        currentPath.pop();
    }
    
    dfs(root, targetSum);
    return result;
}

The Backtracking Pattern

Backtracking always follows this template:

Choose: Add the current element to your working state
Explore: Recursively explore with this choice
Unchoose: Remove the element (restore previous state)

This pattern works for path problems, permutations, combinations, N-Queens, Sudoku, and countless other problems. Master it once, apply it everywhere.

Understanding the Copy Requirement:

Complexity Analysis:

Time: We visit each node once (O(n)), but when we find a valid path, we copy it which takes O(path_length). In a balanced tree, paths are O(log n), giving O(n log n). In a skewed tree, paths are O(n), and if all paths are valid, we have O(n) copies of O(n) paths = O(n²).
Space: The recursion stack is O(h) where h is tree height. The current path is also O(h). The result storage depends on how many valid paths exist.

The elegance of backtracking:

Any-to-Any Paths with Prefix Sums

The most challenging path sum variant is Path Sum III: count all paths that sum to a target, where paths can start and end at any nodes (but must go downward from ancestor to descendant).

This is fundamentally harder because we can't simply track one running sum. A path from node A to node B might be: root → ... → A → ... → B, where only the A→B portion counts.

The Naive Approach:

For each node, consider it as a potential path start and check all downward paths from there. This gives O(n²) or even O(n³) solutions.

The Prefix Sum Insight:

Here's the breakthrough: if we know the sum from root to any node X, we can compute the sum of any path from A to X as:

sum(A to X) = sum(root to X) - sum(root to A)

So to find paths summing to target from any ancestor A to X:

sum(root to X) - sum(root to A) = target sum(root to A) = sum(root to X) - target

If we track all prefix sums (root to each ancestor) in a hash map, we can count valid path starts in O(1)!

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
/**
 * Counts paths that sum to target, where paths can start/end at any nodes
 * but must go downward (parent to child direction only).
 * 
 * Key insight: Use prefix sums. If prefixSum at current node is S,
 * and we've seen a prefix sum of (S - target) at some ancestor,
 * then the path from that ancestor to here sums to target.
 * 
 * Time: O(n) - single traversal with O(1) hash operations
 * Space: O(h) - recursion stack + hash map entries for current path
 */
function pathSumIII(root: TreeNode | null, targetSum: number): number {
    // Map: prefix_sum -> count of ancestors with this prefix sum
    const prefixSumCount = new Map<number, number>();
    
    // Initialize with 0 sum (handles paths starting at root)
    // A prefix sum of 0 exists "before" the root
    prefixSumCount.set(0, 1);
    
    function dfs(node: TreeNode | null, currentSum: number): number {
        if (node === null) {
            return 0;
        }
        
        // Update current prefix sum (root to this node)
        currentSum += node.val;
        
        // Count paths ending here: we need ancestors with sum = currentSum - target
        // If such an ancestor exists, path from it to here sums to target
        const targetPrefixSum = currentSum - targetSum;
        let pathCount = prefixSumCount.get(targetPrefixSum) || 0;
        
        // Add current prefix sum to the map for descendants to use
        prefixSumCount.set(currentSum, (prefixSumCount.get(currentSum) || 0) + 1);
        
        // Explore children
        pathCount += dfs(node.left, currentSum);
        pathCount += dfs(node.right, currentSum);
        
        // CRITICAL: Backtrack! Remove current sum from map
        // This ensures siblings don't see our prefix sum
        const countAfterRemoval = prefixSumCount.get(currentSum)! - 1;
        if (countAfterRemoval === 0) {
            prefixSumCount.delete(currentSum);
        } else {
            prefixSumCount.set(currentSum, countAfterRemoval);
        }
        
        return pathCount;
    }
    
    return dfs(root, 0);
}

Why Initialize with prefixSumCount[0] = 1?

Visualizing the Algorithm:

Consider this tree with targetSum = 8:

Tracing the path 10 → 5 → 3:

At 10: currentSum = 10, looking for 10 - 8 = 2 (not found), add {10: 1}
At 5: currentSum = 15, looking for 15 - 8 = 7 (not found), add {15: 1}
At 3: currentSum = 18, looking for 18 - 8 = 10 (found! count = 1)
- This finds the path 5 → 3 (actually need to check: 18 - 10 = 8 ✓)

Another path: 10 → 5 → 2 → 1:

At 10: currentSum = 10
At 5: currentSum = 15
At 2: currentSum = 17, looking for 17 - 8 = 9 (not found)
At 1: currentSum = 18, looking for 18 - 8 = 10 (found!)
- This finds the path 5 → 2 → 1 (5 + 2 + 1 = 8 ✓)

The backtracking is essential:

Maximum Path Sum — The Ultimate Challenge

This problem is challenging because:

Paths aren't constrained to root-to-leaf or downward-only
A path might go through a node as a "peak" (up from one child, through node, down to other child)
Node values can be negative, complicating greedy decisions

The Key Insight: Contribution vs. Through-Path

At each node, we must distinguish two concepts:

Max contribution up: The maximum sum this node can contribute to a path that continues upward to its parent. This can only include one subtree (or neither), since paths can't fork.
Max through-path: The maximum sum of a path that "peaks" at this node — coming up from left child, through this node, and down to right child. This path is complete and won't extend further.

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
/**
 * Finds the maximum path sum where path can start and end at any nodes.
 * 
 * Key insight: At each node, we track two things:
 * 1. maxGain: max sum this subtree can contribute to parent (single branch)
 * 2. globalMax: max complete path seen so far (might peak at any node)
 * 
 * Time: O(n) - single traversal
 * Space: O(h) - recursion stack
 */
function maxPathSum(root: TreeNode | null): number {
    // Use object to allow mutation in closure (alternative: class field)
    let globalMax = -Infinity;
    
    /**
     * Returns the maximum "gain" this node can contribute to a path
     * that continues upward to its parent.
     * 
     * Side effect: updates globalMax if a better complete path is found
     */
    function maxGain(node: TreeNode | null): number {
        if (node === null) {
            return 0;
        }
        
        // Recursively get max gain from left and right subtrees
        // Use Math.max with 0: negative contributions are "free" to ignore
        // (It's always better to not take a negative-sum path)
        const leftGain = Math.max(0, maxGain(node.left));
        const rightGain = Math.max(0, maxGain(node.right));
        
        // Consider a path that "peaks" at this node:
        // left subtree → this node → right subtree
        // This is a complete path; check if it's the best so far
        const pathThroughNode = node.val + leftGain + rightGain;
        globalMax = Math.max(globalMax, pathThroughNode);
        
        // Return max contribution to parent's path
        // We can only extend in ONE direction (left OR right, not both)
        // because a path can't fork
        return node.val + Math.max(leftGain, rightGain);
    }
    
    maxGain(root);
    return globalMax;
}

The 'Max with Zero' Trick

Why we check globalMax at every node:

The maximum path might peak at any node in the tree — not necessarily the root. So we check at each node: "What if the best path goes left-child → this node → right-child?"

Why maxGain returns only one branch:

When contributing to a parent's path, we can only extend in one direction. Consider:

If we're at node 2, we can contribute to node 1's path by:

Taking the path 3 → 2 → 1 (gain = 3 + 2 = 5)
Or taking the path 4 → 2 → 1 (gain = 4 + 2 = 6)

We can't take 3 → 2 → 4 → ... → 1 because that would require forking at node 2, which isn't a valid path.

Complexity:

Time: O(n) — We visit each node exactly once
Space: O(h) — Recursion stack, where h is tree height (O(log n) to O(n))

Digital Root Problems — A Path Sum Disguise

A fascinating variant is Sum Root to Leaf Numbers: each root-to-leaf path represents a number formed by concatenating node values (like 1→2→3 = 123). Find the total of all such numbers.

This isn't obviously a "sum" problem, but it's structurally identical — we're accumulating information along paths and aggregating at leaves.

The Mathematical Insight:

As we traverse, each digit shifts left (multiply by 10) and adds the new digit:

At root 1: number = 1
At child 2: number = 1 × 10 + 2 = 12
At grandchild 3: number = 12 × 10 + 3 = 123

This is just a different "accumulation function" — instead of adding, we're doing prev * 10 + current.

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
/**
 * Each root-to-leaf path forms a number. Return sum of all such numbers.
 * Example: Paths 1->2->3 and 1->2->4 give 123 + 124 = 247
 * 
 * Key insight: Same structure as path sum, but accumulate with x*10 + digit
 * 
 * Time: O(n)
 * Space: O(h) recursion stack
 */
function sumNumbers(root: TreeNode | null): number {
    function dfs(node: TreeNode | null, currentNumber: number): number {
        if (node === null) {
            return 0;
        }
        
        // Shift current number left by one digit, add this node's value
        currentNumber = currentNumber * 10 + node.val;
        
        // If leaf, this path is complete; return its number
        if (node.left === null && node.right === null) {
            return currentNumber;
        }
        
        // Not a leaf: sum the contributions from both subtrees
        return dfs(node.left, currentNumber) + dfs(node.right, currentNumber);
    }
    
    return dfs(root, 0);
}

Pattern Recognition:

Aspect	Path Sum	Digital Root
Accumulation	sum += node.val	num = num * 10 + node.val
Base case	compare to target	return the number
Aggregation	OR (existence) or list	SUM of all paths

Once you see this structural mapping, you realize that many tree problems are variations on the same theme: propagate context downward, aggregate results upward.

The Generalized Pattern

Many tree problems follow this template:

function solve(node, context):
    if node is null: return base_value
    
    new_context = transform(context, node.val)
    
    if is_leaf(node): return leaf_value(new_context)
    
    return aggregate(
        solve(node.left, new_context),
        solve(node.right, new_context)
    )

Path sum: transform = subtract, aggregate = OR Digital root: transform = *10+, aggregate = SUM Max depth: transform = +1, aggregate = MAX

Real-World Applications

Path sum problems aren't just interview exercises — they model real computational problems across many domains. Understanding these connections helps you recognize where to apply these patterns.

1. Network Cost Optimization:

In a network topology (often tree-shaped for efficiency), path sums represent cumulative latency, bandwidth constraints, or cost. Finding paths within a budget is exactly a path sum problem.

2. Decision Trees in Machine Learning:

3. Compiler Optimization — Expression Trees:

Arithmetic expressions form trees where path computations help with constant folding, strength reduction, and cost estimation. The "cost" to compute a subexpression flows up the tree.

4. Game Trees and Minimax:

In game AI, values propagate up the tree (minimax). While not strictly "sums," the pattern of propagating and aggregating values along paths is identical.

5. Financial Modeling:

Risk models often use tree structures where path sums represent cumulative exposure. Finding paths exceeding risk thresholds is a path sum search.

Path Sum Patterns in Industry Applications
Application	Tree Structure	Path Sum Represents	Query Type
Network Routing	Router topology	Cumulative latency/hops	Find path ≤ budget
ML Decision Trees	Feature splits	Probability/constraints	Classify by leaf
Compiler AST	Expression tree	Computation cost	Optimize total cost
Version Control	Commit history	Accumulated diffs	Find change paths
File Systems	Directory tree	Cumulative size	Find paths > quota

Transferable Skills

Summary and Key Takeaways

Path sum problems form a foundational pattern in tree algorithms. Let's consolidate what we've learned:

Core Concepts Mastered

•Path types: Root-to-leaf, root-to-any, and any-to-any paths each require different algorithmic approaches
•Recursive propagation: Passing accumulated sums downward transforms the problem at each level
•Backtracking: Essential for path enumeration — add on entry, remove on exit
•Prefix sums: Transform O(n²) any-path counting into O(n) using hash maps
•Contribution vs completion: For max path sum, distinguish between contributing to parent and forming a complete path
•Pattern generalization: Most tree problems share the same structure with different transform and aggregate functions

Key Algorithmic Techniques

For existence/count (root-to-leaf): Simple recursion with sum propagation

For enumeration: Backtracking with path reconstruction

For any-path counting: Prefix sums with hash map

For max path (any direction): Track both contribution up and complete path at each node

What's Next:

Page Complete