Path Sum III
Mahabharata — The Hidden Paths — Count All Downward Paths (Not Just Root-to-Leaf) Summing to Target
कोई भी नोड से नोड — नीचे की ओर। Prefix Sum: currSum − target देखा था?॥
*Any node to node — downward direction. Prefix Sum: was currSum − target seen before?*
The Story
Count the number of paths in a binary tree that sum to a target. Paths: - Must go downward (parent to child) - Can start and end at any node (NOT just root-to-leaf)
For tree `[10,5,-3,3,2,null,11,3,-2,null,1]`, targetSum=8: 3 paths.
**Prefix Sum approach (O(n)):** As we do DFS, maintain `currSum` = sum from root to current node.
The number of valid paths ending at the current node = number of **prefix sums** seen so far that equal `currSum - targetSum`.
```java Map<Long, Integer> prefixCount = new HashMap<>(); prefixCount.put(0L, 1); // Empty path has sum 0
int dfs(TreeNode root, long currSum, int target, Map<Long,Integer> preSum) { if (root == null) return 0; currSum += root.val; int count = preSum.getOrDefault(currSum - target, 0); // Paths ending here preSum.merge(currSum, 1, Integer::sum); // Add current prefix count += dfs(root.left, currSum, target, preSum); count += dfs(root.right, currSum, target, preSum); preSum.merge(currSum, -1, Integer::sum); // Remove current prefix (backtrack) return count; } ```
Trace `[10,5,3]` (root=10, left=5, left.left=3), target=8: - At 10: currSum=10. map has {0:1}. count=0 (map has no key 10-8=2). Add 10: map={0:1,10:1} - At 5: currSum=15. count=map.get(15-8=7)=0. Add 15. - At 3: currSum=18. count=map.get(18-8=10)=1! (path 10→5→3 doesn't sum to 8... wait: 5+3=8 ✓ → path is 5→3). Add 18. - Backtrack: remove 18, 15. Add 10 still. - map.get(10-8=2)=0 still. Hmm, let me recount... actually 5+3=8 so yes, currSum at 3 is 18, target=8, looking for 18-8=10 ✓
The Try-All-Start-Nodes DFS
For each node as path start, DFS counting paths summing to target. O(n²).
public int pathSumBrute(TreeNode root, int targetSum) {
if (root == null) return 0;
return pathsFrom(root, targetSum) + pathSumBrute(root.left, targetSum) + pathSumBrute(root.right, targetSum);
}
int pathsFrom(TreeNode root, int target) {
if (root == null) return 0;
int count = root.val == target ? 1 : 0;
return count + pathsFrom(root.left, target-root.val) + pathsFrom(root.right, target-root.val);
}The Prefix-Sum-Map O(n) Wisdom
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> preSum = new HashMap<>();
preSum.put(0L, 1);
return dfs(root, 0L, targetSum, preSum);
}
int dfs(TreeNode root, long currSum, int target, Map<Long, Integer> preSum) {
if (root == null) return 0;
currSum += root.val;
int count = preSum.getOrDefault(currSum - target, 0);
preSum.merge(currSum, 1, Integer::sum);
count += dfs(root.left, currSum, target, preSum);
count += dfs(root.right, currSum, target, preSum);
preSum.merge(currSum, -1, Integer::sum);
return count;
}Step-by-Step Walkthrough
[1,-1], target=0: At 1: currSum=1, look for 1-0=1: not found. At -1: currSum=0, look for 0-0=0: found(count=1, from initial {0:1}). Result=1 ✅ (path 1→-1 sums to 0)Deep Insight
**The 'put(0L, 1)' initialization:** The empty prefix (before root) has sum 0. This allows counting paths that start FROM root: if currSum == target, then currSum - target = 0, which IS in the map → counts the root-to-node path.
**The backtrack step:** `preSum.merge(currSum, -1, Integer::sum)` removes the current node's contribution when backtracking to another branch. Without this, the map would contain sums from irrelevant branches.
**Long for overflow:** Node values can be up to 10^9, and path length up to 10^3. Sum can overflow int. Use Long.
**This is the same prefix sum trick as in the subarray sum equals k (array problem)!** The tree version just uses DFS instead of linear scan, with backtracking to maintain the correct prefix sum window.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(h) | n start nodes × O(n) pathsFrom |
| Optimal | O(n) | O(n) | Single DFS pass; map stores at most h+1 entries at any time |
Pattern Recognition
✅ Path Sum III: prefix sum map + DFS
✅ count += map.get(currSum - target, 0)
✅ Put currSum in map before recursing
✅ Remove currSum from map on backtrack
✅ Initialize map with {0: 1}
**LeetCode Trigger Phrases:**
→ "path sum III" any downward path
→ Subarray sum technique on tree
→ Prefix sum map with DFS backtrackingBhagavad Gita 9.27
यत्करोषि यदश्नासि यज्जुहोषि ददासि यत्। यत्तपस्यसि कौन्तेय तत्कुरुष्व मदर्पणम्॥
Whatever you do, whatever you eat, whatever you offer in sacrifice, whatever you give away, whatever austerity you practice — do that as an offering to Me.
Connection: Path Sum III counts every downward path summing to target — not just root-to-leaf, but any sub-path within the tree. Like the Gita's teaching that every action can be an offering (every action has value), Path Sum III values every partial path, not just complete root-to-leaf journeys. The prefix sum map accumulates running totals as offerings, and recognizes the target-sum paths as those that complete the sacred offering.