Free lesson · DSA Mastery - Interview Prep, End to End
Path Sum III
Path Sum III
Path Sum III removes the root-to-leaf restriction: count the number of downward paths - any start node and any end node, as long as you only move downward - whose values sum to the target. The naive approach reruns a sum-from-each-node search (O(n²)), but the elegant solution uses a prefix-sum hash map carried down the recursion, counting at each node how many earlier prefix sums equal the current running sum minus the target. It fuses tree DFS with the prefix-sum-and-hashmap trick from the array world - a satisfying cross-section technique. We present the O(n²) double-recursion baseline and the O(n) prefix-sum-map solution.
The insight: along any root-to-current path, a downward sub-path ending at the current node has sum target iff some earlier node's prefix sum equals currentPrefix - target. This is exactly the "subarray sum equals k" hash-map trick, applied to the path from the root to the current node. Maintaining a map of prefix-sum frequencies as you descend (and undoing it as you return) counts all qualifying paths in one traversal.
The Problem
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downward (traveling only from parent nodes to child nodes).
Example 1:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths summing to 8 are: 5->3, 5->2->1, and -3->11.
Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3
Constraints:
- The number of nodes in the tree is in the range
[0, 1000]. -10^9 <= Node.val <= 10^9-1000 <= targetSum <= 1000
Approaches Overview
| # | Approach | Time | Space | Verdict |
|---|---|---|---|---|
| 1 | Double recursion (sum from each node) | O(n²) | O(h) | Baseline |
| 2 | Prefix-sum hash map | O(n) | O(h) | Optimal |
The baseline picks each node as a path start and counts downward paths summing to target - O(n²) for the nested traversal. The prefix-sum map carries cumulative-sum frequencies down a single DFS, counting qualifying paths in O(n). The map approach is the elegant, expected optimization.
Approach 1: Double Recursion - Baseline
The Idea
For each node, run a separate downward search counting paths that start at that node and sum to target. The outer recursion visits every node as a potential start; the inner recursion accumulates sums downward from it. Summing across all starts gives the total. O(n²) because each node triggers a fresh O(n) search.
Logic Flowchart
graph TD
A["pathSum(root, target)"] --> B{"root == null?"}
B -->|Yes| C["return 0"]
B -->|No| D["countFrom(root, target) + pathSum(left) + pathSum(right)"]
D --> E["countFrom(node, remaining): add 1 if node.val == remaining, then recurse with remaining - node.val"]
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
This flowchart shows the double recursion. For each node we count downward paths starting there that sum to target, then recurse to treat every other node as a start.
Code
public static int pathSum(TreeNode root, int targetSum) {
if (root == null) return 0;
return countFrom(root, targetSum)
+ pathSum(root.left, targetSum)
+ pathSum(root.right, targetSum);
}
private static int countFrom(TreeNode node, long remaining) {
if (node == null) return 0;
int count = (node.val == remaining) ? 1 : 0; // path ending here
return count
+ countFrom(node.left, remaining - node.val)
+ countFrom(node.right, remaining - node.val);
}
This Java code counts, for each node as a starting point, downward paths summing to target, then recurses so every node serves as a start. The nested search makes it quadratic.
Complexity
Time: O(n²) (O(n) starts, each an O(n) search). Space: O(h). The map approach reaches O(n).
Approach 2: Prefix-Sum Hash Map - Optimal
The Idea
Do a single DFS carrying the running prefix sum from the root to the current node, plus a hash map of how many times each prefix-sum value has occurred along the current path. At each node, the number of downward paths ending here with sum target equals the count of prefix - target already in the map. Add the current prefix to the map before recursing, and remove it after (backtrack) so it only counts ancestors on the active path. Seed the map with {0: 1} to catch paths starting at the root.
Logic Flowchart
graph TD
A["map = {0:1}; dfs(root, 0)"] --> B{"node == null?"}
B -->|Yes| C["return 0"]
B -->|No| D["prefix += node.val"]
D --> E["count = map.getOrDefault(prefix - target, 0)"]
E --> F["map[prefix]++ ; recurse left + right"]
F --> G["map[prefix]-- (backtrack)"]
G --> H["return count + left + right"]
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
This flowchart shows the prefix-sum map approach. Carrying a running prefix sum, at each node we add the number of earlier prefix sums equal to prefix minus target, then record the current prefix, recurse, and remove it on the way back.
Code
public static int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> prefixCount = new HashMap<>();
prefixCount.put(0L, 1); // empty prefix: enables root-started paths
return dfs(root, 0L, targetSum, prefixCount);
}
private static int dfs(TreeNode node, long prefix, int target, Map<Long, Integer> prefixCount) {
if (node == null) return 0;
prefix += node.val; // running sum from root to here
int count = prefixCount.getOrDefault(prefix - target, 0); // paths ending here
prefixCount.merge(prefix, 1, Integer::sum); // record this prefix
count += dfs(node.left, prefix, target, prefixCount);
count += dfs(node.right, prefix, target, prefixCount);
prefixCount.merge(prefix, -1, Integer::sum); // backtrack: leave the path
return count;
}
// Usage:
// pathSum([10,5,-3,3,2,null,11,3,-2,null,1], 8) -> 3
This Java code carries a running prefix sum and a map of prefix-sum frequencies. At each node it adds the count of the prefix minus target, records the current prefix, recurses, and decrements the prefix count when leaving the node.
Step-by-Step Walkthrough
A frame-by-frame trace illustrating the path 10 -> 5 -> 3 with target = 8:
graph LR
F0["root 10: prefix=10; need prefix-8=2 in map (only {0:1}) → 0; map{0:1,10:1}"]
F1["5: prefix=15; need 15-8=7 → 0; map adds 15:1"]
F2["3: prefix=18; need 18-8=10 → map has 10:1 → count 1 (path 5->3)"]
F3["...other branches add 5->2->1 and -3->11 → total 3"]
F0 --> F1 --> F2 --> F3
style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
This walkthrough shows the path ten, five, three with target eight. At node three the running prefix is eighteen, and eighteen minus eight is ten, which exists in the map, revealing the path five to three. Other branches contribute two more, totaling three.
Result: 3.
Complexity
Time: O(n) - one DFS, O(1) map work per node. Space: O(h) for the recursion and the active-path prefix entries.
Complexity Comparison
| Approach | Time | Space | Key Idea | When to Use |
|---|---|---|---|---|
| Double recursion | O(n²) | O(h) | Search from every start | Small trees, clarity |
| Prefix-sum map | O(n) | O(h) | Count prefix - target seen |
Optimal |
The prefix-sum map is optimal, collapsing the nested search into a single linear pass by reusing cumulative sums. It's the tree analogue of the array "subarray sum equals k" technique - recognizing that connection is the key insight.
Variations & Follow-ups
Why seed the map with {0: 1}?
The entry {0: 1} represents the empty prefix before the root. It lets a path that starts at the root itself be counted: when the running prefix from the root equals target, prefix - target is 0, and the seeded entry contributes 1. Without it, you'd miss every path beginning at the root. It's the same boundary seed used in the array prefix-sum-equals-k pattern.
Why must you decrement the map entry when leaving a node?
The map should reflect prefix sums of nodes on the current root-to-node path only - the ancestors of the node being processed. When you finish a node's subtree and return, that node is no longer an ancestor of the nodes you'll visit next (in sibling branches), so its prefix must be removed. Skipping the decrement would let paths "pass through" nodes that aren't actually ancestors, overcounting. This backtracking of the map mirrors the path-list backtracking in Path Sum II.
How is this the tree version of "subarray sum equals k"?
In an array, the number of subarrays ending at index i with sum k equals the count of prefix sums equal to prefix[i] - k. Here, the "array" is the path from the root to the current node, and a downward path ending at the current node corresponds to a subarray of that path. The same hash-map-of-prefix-sums counts them in O(1) per node. The tree just supplies a dynamically changing "array" as you descend, which the backtracking keeps consistent.
Why use long for the prefix sum?
Node values range up to 10^9 in magnitude and a path can have up to ~1000 nodes, so the cumulative prefix sum can exceed the int range and overflow. Accumulating the prefix in a long (and keying the map by Long) avoids wraparound that would corrupt the prefix - target lookups. This is the same overflow discipline seen throughout the course applied to a path's running total.
What about edge cases?
- Empty tree: 0.
- Negative values (Example 1): The running sum can decrease; the map handles it naturally.
- Single node equal to target: Counted via the
{0:1}seed. - Multiple paths through the same node: Each counted separately by the frequency map.
Common Interview Pitfalls
- Forgetting the
{0:1}seed. Misses root-started paths. - Not backtracking the map. Overcounts by treating non-ancestors as ancestors.
- Integer overflow. Use
longfor the prefix sum given the large value range. - Counting upward or cross paths. Only downward paths count; the DFS naturally enforces this.
Why This Topic Matters
Path Sum III is a standout cross-section fusion: it applies the array world's prefix-sum-plus-hashmap trick to a tree path, turning an O(n²) search into O(n). It deepens the preorder context-passing theme (now carrying a map down and backtracking it) and reinforces that recognizing a familiar subproblem (subarray sum equals k) inside an unfamiliar setting is often the key to the optimal solution.
The next topic, Longest Univalue Path, shifts toward measuring a path property rather than enumerating paths: find the length of the longest path where all nodes have the same value (the path may pass through a node, connecting its left and right arms). This needs a postorder-flavored return (each node reports the longest same-value arm extending downward) combined with an update of a global best at each node - previewing the "return one thing, update a global" pattern that dominates the postorder sub-group, applied here within the preorder grouping as a bridge.