Common Tree Patterns & Problem Types
Path Sum Problems
Read aloud is unavailable in this browser.
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.
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 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) |
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)?"
123456789101112131415161718192021222324252627282930313233343536
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);}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.
12345678910111213141516171819202122232425262728293031323334353637383940414243
/** * 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;}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)!
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
/** * 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);}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:
10
/
5 -3
/ \
3 2 11
/ \
3 -2 1
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.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
/** * 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 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:
1
/
2
/
3 4
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.
1234567891011121314151617181920212223242526272829
/** * 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.
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.
| 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 |
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.
KEEP LEARNING
There’s more to understand.
You’re reading the introduction. Create a free account to read the complete lesson, save notes and keep track of your progress.