Skip to content

Prefix Sums on Trees

The Array Trick That Transfers Directly

You already know this idea on arrays: given an array, find the number of contiguous subarrays that sum to \(k\). The solution is a running prefix sum plus a hash map tracking how many times each prefix sum has appeared. When your current prefix sum is \(S\), any earlier prefix sum equal to \(S - k\) marks the start of a valid subarray.

A root-to-leaf path in a tree IS an array. And any subpath along that root-to-leaf path IS a contiguous subarray. So the exact same technique works — you just DFS instead of iterating left to right.

This is the single most tested tree concept in online assessments. If you learn one technique from this chapter, make it this one.

Prefix sums along a root-to-leaf path, with the hash map tracking counts of each prefix sum

Problem: Path Sum III (LC 437)

Problem: Given the root of a binary tree and an integer \(targetSum\), return the number of paths where the values along the path sum to \(targetSum\). The path does not need to start at the root or end at a leaf, but it must go downward (from parent to child).

        10
       /  \
      5   -3
     / \     \
    3   2    11
   / \   \
  3  -2   1

\(targetSum = 8\). Answer: 3 (the paths: \(5 \to 3\), \(5 \to 2 \to 1\), \(-3 \to 11\)).

Why Brute Force Breaks

The naive approach: for every node, start a new DFS and count all downward paths summing to \(targetSum\). That's \(O(n)\) nodes each launching an \(O(n)\) DFS. Total: \(O(n^2)\).

For \(n = 10^5\) nodes (the constraint on LC 437), \(O(n^2)\) is too slow. You need \(O(n)\).

The Insight: A path from node \(A\) down to node \(B\) has sum \(targetSum\) exactly when \(prefixSum(B) - prefixSum(A) = targetSum\). Track prefix sums in a hash map as you DFS — identical to the subarray sum problem on arrays.

The Technique

As you DFS from the root, maintain a running prefix sum — the sum of all node values from the root to the current node. At each node:

  1. Compute \(runningSum = runningSum + node.val\)
  2. Check how many times \((runningSum - targetSum)\) has appeared as a prefix sum above you. Each occurrence is one valid path ending here.
  3. Add \(runningSum\) to the hash map.
  4. Recurse left and right.
  5. Remove \(runningSum\) from the hash map (backtrack — this prefix sum is only valid for nodes in this subtree).

Step 5 is what makes this work on a tree instead of an array. On an array, you never backtrack because you only move forward. On a tree, when you finish a subtree and move to a sibling, the prefix sums from the finished subtree are no longer on your path.

Full Trace

Tree with \(targetSum = 8\):

        10
       /  \
      5   -3
     / \     \
    3   2    11
   / \   \
  3  -2   1

The hash map starts with \(\{0: 1\}\) — this represents the "empty prefix" before the root, so a path starting at the root itself can be detected.

Step Node runningSum runningSum - target Map lookup Paths found Map after insert
1 10 10 2 0 0 {0:1, 10:1}
2 5 15 7 0 0 {0:1, 10:1, 15:1}
3 3 18 10 1 (key 10 exists) 1 {0:1, 10:1, 15:1, 18:1}
4 3 21 13 0 0 {0:1, 10:1, 15:1, 18:1, 21:1}
— backtrack from 3 (leaf) {0:1, 10:1, 15:1, 18:1}
5 -2 16 8 0 0 {0:1, 10:1, 15:1, 18:1, 16:1}
— backtrack from -2 {0:1, 10:1, 15:1, 18:1}
— backtrack from 3 {0:1, 10:1, 15:1}
6 2 17 9 0 0 {0:1, 10:1, 15:1, 17:1}
7 1 18 10 1 (key 10 exists) 1 {0:1, 10:1, 15:1, 17:1, 18:1}
— backtrack from 1 {0:1, 10:1, 15:1, 17:1}
— backtrack from 2 {0:1, 10:1, 15:1}
— backtrack from 5 {0:1, 10:1}
8 -3 7 -1 0 0 {0:1, 10:1, 7:1}
9 11 18 10 1 (key 10 exists) 1 {0:1, 10:1, 7:1, 18:1}
— backtrack from 11 {0:1, 10:1, 7:1}
— backtrack from -3 {0:1, 10:1}

Total paths found: \(1 + 1 + 1 = 3\).

Manual verification: - Path \(5 \to 3\): sum \(= 5 + 3 = 8\). Valid. - Path \(5 \to 2 \to 1\): sum \(= 5 + 2 + 1 = 8\). Valid. - Path \(-3 \to 11\): sum \(= -3 + 11 = 8\). Valid.

No other downward path sums to 8. Answer confirmed.

The Code

void dfs(TreeNode* node, long long runningSum, int targetSum,
         unordered_map<long long, int>& prefixSumCount, int& totalPaths) {
    if (!node) return;

    runningSum += node->val;
    totalPaths += prefixSumCount[runningSum - targetSum];
    prefixSumCount[runningSum]++;

    dfs(node->left, runningSum, targetSum, prefixSumCount, totalPaths);
    dfs(node->right, runningSum, targetSum, prefixSumCount, totalPaths);

    prefixSumCount[runningSum]--;
}

int countPathsWithSum(TreeNode* root, int targetSum) {
    unordered_map<long long, int> prefixSumCount;
    prefixSumCount[0] = 1;
    int totalPaths = 0;
    dfs(root, 0, targetSum, prefixSumCount, totalPaths);
    return totalPaths;
}

Complexity: \(O(n)\) time, \(O(n)\) space for the hash map and recursion stack.

Bonus: Count Good Nodes (LC 1448)

Problem: A node is "good" if no node on the path from the root to that node has a value greater than it. Return the count of good nodes.

This is a simpler top-down pass. Instead of a prefix sum, pass the maximum value seen so far from root to the current node. A node is good if \(node.val \geq maxSoFar\).

int countGoodNodes(TreeNode* node, int maxSoFar) {
    if (!node) return 0;
    int isGood = (node->val >= maxSoFar) ? 1 : 0;
    int newMax = max(maxSoFar, node->val);
    return isGood + countGoodNodes(node->left, newMax) + countGoodNodes(node->right, newMax);
}

int countGoodNodes(TreeNode* root) {
    return countGoodNodes(root, root->val);
}

Same pattern: carry state downward, make a decision at each node. No hash map needed — just a single integer flowing down.

The unifying idea: Top-down DFS is about passing context from ancestor to descendant. Sometimes that context is a single value (max so far). Sometimes it's an entire hash map (prefix sum counts). The shape of the recursion is identical.

Try It

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3

Predict before running: What happens if every node has value 0 and \(targetSum = 0\)? Every subpath sums to 0, so the answer explodes. On a balanced tree of \(n\) nodes, how many such paths exist?

Challenge: Modify the prefix sum approach to also print each valid path, not just count them. You'll need to maintain the actual path (a vector of node values) alongside the prefix sum map.

Edge Cases to Watch For

  • Forgetting to backtrack (decrement the hash map): After recursing into both children, you MUST decrement prefixSumCount[runningSum]. Without this, prefix sums from a finished subtree leak into sibling subtrees and produce wrong counts.
  • Forgetting the initial {0: 1} entry: The hash map must start with prefixSumCount[0] = 1. This represents the empty prefix before the root. Without it, you miss paths that start at the root itself (where runningSum == targetSum).
  • Integer overflow: Node values can be negative, and running sums can grow large. Use long long for runningSum to avoid overflow when the tree has up to \(10^5\) nodes with values up to \(10^9\).

Platform Connection — Fix the Equation: This technique is the tree version of the "Fix the Equation" pattern used in array problems. On arrays: fix index \(j\), ask "how many \(i < j\) have prefixSum[i] == prefixSum[j] - target?" On trees: fix the current node, ask the same question using the running sum from root. The hash map stores the same frequencies — the only difference is the DFS path replaces the linear scan, and you backtrack the map on the way up.

Problems

Problem Link Difficulty
LC 437 --- Path Sum III leetcode.com/problems/path-sum-iii Medium
LC 1448 --- Count Good Nodes in Binary Tree leetcode.com/problems/count-good-nodes-in-binary-tree Medium
LC 560 --- Subarray Sum Equals K leetcode.com/problems/subarray-sum-equals-k Medium
LC 687 --- Longest Univalue Path leetcode.com/problems/longest-univalue-path Medium