Definition
- Count Paths for a Sum counts every downward path in a binary tree whose node values sum to a target, where paths can start and end at any node.
- Prefix sum technique stores a running sum from the root to the current node and a HashMap of how many times each prefix sum value has appeared along the current path.
- Path counting at each node equals the number of ancestor prefix sums equal to
currentSum - target, read from the map in O(1). - Rollback decrements the current node's prefix count after visiting both children, keeping sibling branches isolated.
- Complexity is O(n) time and O(h) space where h is the tree height.
At the National Bank of India, a stream of charges flows down a chain of approval desks. Auditors want to count every contiguous downward stretch of charges that adds up to a flagged amount. A stretch can start at any desk, not just the top. The auditor keeps a running total and remembers how often each total has appeared. Whenever the running total minus the flagged amount has appeared before, each earlier appearance marks the start of a matching stretch.
Understanding the Concepts
What is the Count Paths for a Sum problem?
Given a binary tree and a target sum, count all paths where the node values add up to the target. The paths must go downward (from parent to child), but they do not need to start at the root or end at a leaf. Any node can be the start or end of a path.
For example, in a tree where the root is 10 with children 5 and -3, and node 5 has children 3 and 2, and the target is 8, the valid paths are [5, 3] and [10, 5, 3, -10, ...] (if such nodes exist).
package com.bank.audit;
public class TreeNode {
int value;
TreeNode left;
TreeNode right;
public TreeNode(int value) {
this.value = value;
}
}
package com.bank.audit;
import java.util.HashMap;
import java.util.Map;
/**
* Counts all downward paths in a binary tree that sum to a target.
* Uses the prefix-sum technique for O(n) performance.
*/
public class PathSumCounter {
public static int countPaths(TreeNode root, int target) {
Map<Long, Integer> prefixCounts = new HashMap<>();
prefixCounts.put(0L, 1); // seed for paths starting at root
return dfs(root, 0L, target, prefixCounts);
}
private static int dfs(TreeNode node, long currentSum, int target,
Map<Long, Integer> prefixCounts) {
if (node == null) return 0;
currentSum += node.value;
int count = prefixCounts.getOrDefault(currentSum - target, 0);
prefixCounts.merge(currentSum, 1, Integer::sum);
count += dfs(node.left, currentSum, target, prefixCounts);
count += dfs(node.right, currentSum, target, prefixCounts);
prefixCounts.merge(currentSum, -1, Integer::sum); // rollback
return count;
}
public static void main(String[] args) {
// 10
// / \
// 5 -3
// / \ \
// 3 2 11
// / \ \
// 3 -2 1
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(-3);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(2);
root.right.right = new TreeNode(11);
root.left.left.left = new TreeNode(3);
root.left.left.right = new TreeNode(-2);
root.left.right.right = new TreeNode(1);
System.out.println("Paths summing to 8: " + countPaths(root, 8));
}
}
Paths summing to 8: 3
Why is the brute-force approach too slow?
The brute-force approach tries every node as a potential path start and walks downward from each, summing values and counting matches. For a balanced tree this is O(n log n), but for a skewed tree (essentially a linked list) it becomes O(n^2) because each node walks to every descendant.
The prefix-sum technique eliminates the repeated work by computing the answer for each node in O(1) using the map lookup.
// Brute force: O(n^2) on skewed trees
public static int countPathsBrute(TreeNode root, int target) {
if (root == null) return 0;
return countFromNode(root, target, 0)
+ countPathsBrute(root.left, target)
+ countPathsBrute(root.right, target);
}
private static int countFromNode(TreeNode node, int target, long currentSum) {
if (node == null) return 0;
currentSum += node.value;
int count = (currentSum == target) ? 1 : 0;
count += countFromNode(node.left, target, currentSum);
count += countFromNode(node.right, target, currentSum);
return count;
}
How does the prefix-sum technique work internally?
The key insight comes from the subarray sum problem on arrays. If you have a running prefix sum from the start to position i, and you know that the prefix sum at some earlier position j equals prefixSum[i] - target, then the subarray from j+1 to i sums to the target.
The same logic applies to tree paths. The running prefix sum from the root to the current node is currentSum. If some ancestor had a prefix sum equal to currentSum - target, then the path from that ancestor's child down to the current node sums to the target.
The HashMap stores how many ancestors have each prefix sum value. At each node, we look up currentSum - target in the map to count valid paths ending at this node.
// Prefix sum example on a path: root(10) -> left(5) -> left(3)
// Prefix sums: 10, 15, 18
// Target = 8
//
// At node 3 (currentSum = 18):
// currentSum - target = 18 - 8 = 10
// prefixCounts[10] = 1 (from root node)
// So there is 1 path ending here: [5, 3] (sum = 8)
//
// At node 5 (currentSum = 15):
// currentSum - target = 15 - 8 = 7
// prefixCounts[7] = 0
// No paths ending here sum to 8
Why is the seed value important?
The map is seeded with prefixCounts.put(0L, 1) before the traversal begins. This seed handles the case where the path from the root to the current node itself sums to the target.
Without the seed, currentSum - target would be zero, and the map would return zero for the count, missing a valid path.
// Without seed:
// Tree: root(8), target = 8
// At root: currentSum = 8, lookup currentSum - target = 0
// prefixCounts[0] = 0 (missing!) -> count = 0
// BUG: misses the path [8] which sums to 8
// With seed:
// prefixCounts = {0: 1}
// At root: currentSum = 8, lookup currentSum - target = 0
// prefixCounts[0] = 1 -> count = 1
// CORRECT: counts the path [8]
Why is the rollback necessary?
After visiting both children of a node, we decrement the current node's prefix count in the map. This rollback ensures that sibling branches do not see each other's prefix sums.
Without rollback, a prefix sum from the left subtree could be counted when processing the right subtree, falsely creating a path that jumps from the left branch to the right branch, which violates the downward-only constraint.
// Without rollback:
// 5
// / \
// 3 3
// Target = 8
//
// Processing left child (3): currentSum = 8, add prefixCounts[8] = 1
// Processing right child (3): currentSum = 8
// lookup currentSum - target = 0 -> prefixCounts[0] = 1 (correct)
// But prefixCounts[8] from left child is still in the map!
// This could cause false positives in deeper trees.
// With rollback:
// After processing left subtree, decrement prefixCounts[8] back
// Right subtree starts with a clean map for this branch
What are the edge cases?
The important edge cases are:
- Null tree: return 0.
- Single node equal to target: the path is just that node. The seed handles this.
- Negative values: node values can be negative, which means prefix sums can decrease. This is exactly why the prefix-sum technique is needed instead of simple pruning.
- Multiple paths through the same node: a node can be part of multiple valid paths starting from different ancestors.
- Target of zero: valid paths are those where the sum cancels to zero, which happens when the current prefix sum equals an earlier prefix sum.
package com.bank.audit;
public class PathSumEdgeCases {
public static void main(String[] args) {
// Single node = target
TreeNode single = new TreeNode(8);
System.out.println("Single node: " + PathSumCounter.countPaths(single, 8));
// Negative values
// 1
// / \
// -2 3
TreeNode neg = new TreeNode(1);
neg.left = new TreeNode(-2);
neg.right = new TreeNode(3);
System.out.println("Target -1: " + PathSumCounter.countPaths(neg, -1));
// Target zero with cancellation
// 5
// /
// -5
TreeNode zero = new TreeNode(5);
zero.left = new TreeNode(-5);
System.out.println("Target 0: " + PathSumCounter.countPaths(zero, 0));
}
}
Single node: 1
Target -1: 1
Target 0: 1
What are common mistakes?
The most common mistake is forgetting to roll back the prefix count, which causes false path counts across sibling branches.
// WRONG: no rollback
private static int dfsWrong(TreeNode node, long currentSum, int target,
Map<Long, Integer> prefixCounts) {
if (node == null) return 0;
currentSum += node.value;
int count = prefixCounts.getOrDefault(currentSum - target, 0);
prefixCounts.merge(currentSum, 1, Integer::sum);
count += dfsWrong(node.left, currentSum, target, prefixCounts);
count += dfsWrong(node.right, currentSum, target, prefixCounts);
// BUG: missing rollback! Left subtree prefixes leak into right subtree.
return count;
}
// CORRECT: rollback after processing children
prefixCounts.merge(currentSum, -1, Integer::sum); // rollback
return count;
Another common mistake is forgetting the seed, which misses paths that start at the root.
How is this different from the root-to-leaf path sum?
The root-to-leaf path sum problem (Path Sum I/II) requires paths that start at the root and end at a leaf. Count Paths for a Sum allows paths to start and end at any node, making it a harder problem.
| Aspect | Root-to-Leaf Path Sum | Count Paths for a Sum |
|---|---|---|
| Start | Must be root | Any node |
| End | Must be a leaf | Any node |
| Path direction | Downward | Downward |
| Approach | Simple DFS with running sum | Prefix sum with HashMap |
| Time | O(n) | O(n) |
// Root-to-leaf path sum: simple DFS
public static boolean hasPathSum(TreeNode root, int target) {
if (root == null) return false;
if (root.left == null && root.right == null) {
return root.value == target;
}
return hasPathSum(root.left, target - root.value)
|| hasPathSum(root.right, target - root.value);
}
What should a senior engineer know?
A senior engineer should know that this prefix-sum technique is the tree version of the subarray sum equals k problem on arrays. The core idea is identical: maintain a prefix sum and a frequency map, and at each position look up currentSum - target in the map.
Using long for the running sum prevents integer overflow when node values are large. In production systems like fraud detection, charge amounts can sum to large values, and overflow would silently produce wrong counts.
The space complexity is O(h) where h is the tree height, because the map holds at most h entries (one per ancestor on the current path). For a balanced tree, h = O(log n). For a skewed tree, h = O(n).
What are common interview follow-up questions?
Interviewers often ask:
- Can you print all the paths instead of just counting them? Yes, maintain a list of nodes on the current path and capture subpaths when a match is found.
- What if paths can go upward too? Then you need a different approach, like checking every pair of nodes using LCA.
- How does this relate to the subarray sum problem? They use the same prefix-sum plus HashMap technique.
- What if the tree is very deep? The recursion might cause a stack overflow. Use an iterative DFS with an explicit stack.
Visual Overview
Tree:
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Target = 8
Prefix sums from root:
10 -> 15 -> 18 -> 21
10 -> 15 -> 18 -> 16
10 -> 15 -> 17 -> 18
10 -> 7 -> 18
Paths summing to 8:
[5, 3] (prefixSum 15 to 18, diff = 18-10 = 8)
[10, 5, 3, -2, ...] check prefix diffs
[-3, 11] (prefixSum 7 to 18, diff = 18-10 = 8)
┌──────────────────────────────────────┐
│ Prefix Sum Technique │
│ │
│ 1. Seed map: {0: 1} │
│ 2. At each node: │
│ currentSum += node.value │
│ count += map[currentSum - target]│
│ map[currentSum]++ │
│ 3. Recurse left and right │
│ 4. Rollback: map[currentSum]-- │
│ │
│ Seed ensures root-starting paths │
│ Rollback isolates sibling branches │
└──────────────────────────────────────┘
Key Takeaway
Count Paths for a Sum counts every downward path in a binary tree whose node values add up to a target, where a path can start and end at any node. The brute-force approach tries every node as a start and walks downward, which is O(n^2) on a skewed tree. The prefix-sum technique reduces this to O(n) by maintaining a running sum from the root and a HashMap of prefix sum frequencies.
The two details that matter most are seeding and rollback. Seeding the map with zero counted once ensures that paths starting at the root are not missed. Rolling back the current node's prefix count after visiting both children ensures that sibling branches do not borrow each other's prefix sums, which would falsely count paths that jump across branches.
At the National Bank of India, Rajesh used this technique to scan charge chains for fraud. Each desk in an approval chain added a charge amount, and the audit system needed to count every contiguous downward run of charges that summed to a flagged amount. He stored charges as BigDecimal, converted them to long cents for the HashMap, seeded the map correctly, and rolled back after each desk.
The prefix-sum technique is the tree version of the subarray sum equals k problem on arrays. The core idea is identical: maintain a prefix sum and a frequency map, look up currentSum - target at each position, and roll back when leaving a scope. This structural insight connects array and tree problems in a way that makes both easier to solve.
Remember one sentence: prefix sum plus frequency map, seed with zero, roll back after children, and every path match costs O(1).
---