A cost-center tree stores each team’s ledger delta — charges, and refunds as negatives. Ops wants how many downward reporting chains summed to exactly target, a credit they want to flag. The first version started a sum-walk from every node: for each employee, walk every descendant path. A dozen seats returned before the page painted. A million-node imported org chart was still restarting walks when the request timed out.

Count every downward path whose values sum to target. Path Sum asks whether one root-to-leaf walk hits the target. This prompt starts and ends anywhere, parent to child only — a leaf is not required. Prefix sums already turn a slice sum into subtraction. Nested “start a DFS from every node” uses that identity and still pays O(n²) walks. Subarray Sum Equals K is the same complement in prefix space on a line. Here the line is the current root-to-node path.

This is an interview writeup, not a prefix-sum or hashing lecture. The prefix post owns exclusive vs inclusive tables. The hash table post owns buckets and collisions. The binary tree post owns shape and traversals. Here we store prefix → how many times it appeared on this path — increment on enter, decrement on leave.

The problem

Given the root of a binary tree and an int targetSum, return how many downward paths sum to targetSum. A path is parent to child only. It does not have to start at the root or end at a leaf. Overlapping paths each count. An empty tree is 0. A single node is a path.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1     target = 8  →  3   (5→3, 5→2→1, -3→11)

    1
   / \
  2   3       target = 3  →  2   (1→2 and 3)

[8]           target = 8  →  1
[]            target = 0  →  0

Note: Path Sum is a yes/no on root-to-leaf only. Answering that here undercounts: 5→3 never starts at the root, and a lone 8 is a legal one-node path. Refunds make the running sum non-monotonic, so you cannot prune with “already too big.”

Nested starts are the honest brute force

At every node, walk every downward path that begins there, then do the same work in both children. Every downward slice is visited once. Correct. Quadratic on a spine: each ancestor re-walks the same descendants.

int pathSumNested(TreeNode root, int targetSum) {
    if (root == null) {
        return 0;
    }
    return countFrom(root, targetSum)
            + pathSumNested(root.left, targetSum)
            + pathSumNested(root.right, targetSum);
}

int countFrom(TreeNode node, long remain) {
    if (node == null) {
        return 0;
    }
    int hit = remain == node.val ? 1 : 0;
    return hit
            + countFrom(node.left, remain - node.val)
            + countFrom(node.right, remain - node.val);
}

At a dozen nodes this is a rounding error. At n in the tens of thousands you paid a nested start for a question a prefix map answers in expected constant time per node: how many prefixes on this root-to-node path equal P - target?

One DFS: store prefix counts, look up P - target, decrement on leave

Walk with a running total P. A downward path ending here sums to target exactly when some ancestor prefix equals P - target. That is the same lookup as Subarray Sum Equals K. The tree twist: the map may hold only prefixes on the current path, so sibling branches do not steal counts.

Seed the map with prefix 0 seen once, so a path that starts at the current node has a partner. Then, at each node:

  • Add node.val into P.
  • Add map.getOrDefault(P - target, 0) to the answer.
  • Record this P: increment the count.
  • Recurse left, then right.
  • Decrement this P before returning — you are leaving this path.

You never restart a walk from every node. Look up before you increment so a prefix cannot pair with itself as a zero-length path.

target = 8   seed  map {0: 1}   P = 0   answer = 0

10   P=10   need=2    miss, put 10 → 1
  5   P=15   need=7    miss, put 15 → 1
    3   P=18   need=10   hit 1 (5→3), put 18 → 1
      3   P=21   miss;  -2 P=16 miss;  leave 3
    2   P=17   need=9    miss, put 17 → 1
      1   P=18   need=10  hit 1 (5→2→1);  leave 2
  leave 5
 -3   P=7    need=-1   miss, put 7 → 1
   11   P=18   need=10  hit 1 (-3→11);  leave -3
leave 10
answer = 3

The three hits are 5→3, 5→2→1, and -3→11. The Java is that walk:

int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0L, 1);
    return dfs(root, 0L, targetSum, prefixCount);
}

int dfs(TreeNode node, long prefix, int target, Map<Long, Integer> prefixCount) {
    if (node == null) {
        return 0;
    }
    prefix += node.val;
    int answer = prefixCount.getOrDefault(prefix - target, 0);
    prefixCount.put(prefix, prefixCount.getOrDefault(prefix, 0) + 1);
    answer += dfs(node.left, prefix, target, prefixCount);
    answer += dfs(node.right, prefix, target, prefixCount);
    prefixCount.put(prefix, prefixCount.get(prefix) - 1);
    return answer;
}

Time is expected O(n) — one visit per node, one expected-O(1) lookup and put. Space is O(n) for the map and the call stack on a spine. Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.

Note: Seed prefix 0 with count 1. Without it, a path that starts at the node you are on never finds a partner — a lone 8 with target = 8 would answer 0. Decrement the current prefix when you leave. The array version never backtracks; a tree does. Leave a left-child prefix in the map and the right sibling treats it as an ancestor. Look up before you increment. If you put first, a lone prefix pairs with itself as a zero-length path. That is not a node. Loudest when target = 0.

What interviewers usually poke next

  • Return the paths, not the count. A map of prefix → count forgets which ancestors those prefixes sat on. Keep the nodes on the current walk and emit copies when a lookup hits.
  • Root-to-leaf only. That is Path Sum. Drop the map; a remaining-sum walk that must finish at a leaf is enough.
  • The path need not go down. Maximum Path Sum allows a fork through a node. Prefixes on a parent-to-child walk do not cover that shape.
  • The array version. Subarray Sum Equals K is this map on a line — no decrement, because there is no sibling branch.
  • Overflow. prefix += node.val in int wraps. The walk above uses long so a deep spine of large values still looks up the real complement.

You are done with this problem when you can say, out loud, why nested starts are correct, why Path Sum’s root-to-leaf check is the wrong contract, why the map is seeded with prefix 0, and why the current prefix is decremented on the way back.