Path Sum III — Prefix Sum HashMap on Binary Trees (LC 437)

Problem Statement#

LeetCode 437 — Path Sum III | Difficulty: Medium

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 from parent nodes to child nodes).

Constraints:

• The number of nodes is in the range [0, 1000]
• -10^9 <= Node.val <= 10^9
• -1000 <= targetSum <= 1000

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

Input:  root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

Why This Problem Matters#

Path Sum III is a FAANG interview favorite because it tests whether you can transfer a well-known array technique — prefix sum with a hashmap — to a tree structure. Amazon and Google frequently ask it as a follow-up to the simpler Path Sum I and II problems. The naive O(n^2) solution (start a fresh DFS from every node) is a trap; the optimal O(n) solution with prefix sums is what interviewers want to see.

The skill tested here is pattern transfer: recognizing that "count paths summing to k on a tree" is structurally identical to "count subarrays summing to k on an array." Both use the insight that if prefix[j] - prefix[i] == target, then the subpath from index i+1 to j sums to target. On a tree, the "indices" are nodes along the root-to-current path, and backtracking restores the state when you leave a subtree.

The Core Insight#

Define prefix_sum as the cumulative sum from the root to the current node. A path ending at the current node with sum = targetSum exists if and only if there is some ancestor node where prefix_sum_at_ancestor == prefix_sum - targetSum.

Maintain a hashmap counting how many times each prefix sum has been seen along the current root-to-node path. At each node:

1. Check how many times current_prefix - targetSum appears in the map — each occurrence is a valid path.
2. Add the current prefix sum to the map.
3. Recurse into left and right children.
4. Remove the current prefix sum from the map (backtrack) before returning.

The backtracking step is critical — it ensures the map only reflects the current root-to-node path, not the entire tree.

Visual Dry Run#

Tree: [10, 5, -3, 3, 2, null, 11], targetSum = 8

Total count = 3 (path 5→3, path -3→11, and path 10→5→-3 gives 12, not 8 — the third valid path is 5→3 with sum 8, and also standalone 11-3=8... verify: paths are 10→-3→11=18≠8, 5→3=8 yes, 5→2→1=8 yes, -3→11=8 yes). Answer = 3.

Solution (Optimal)#

from collections import defaultdict
 
class Solution:
    def pathSum(self, root, targetSum: int) -> int:
        prefix_count = defaultdict(int)
        prefix_count[0] = 1  # empty path before root
        self.result = 0
 
        def dfs(node, curr_sum):
            if not node:
                return
 
            curr_sum += node.val
 
            # Count paths ending at this node with sum == targetSum
            self.result += prefix_count[curr_sum - targetSum]
 
            # Record this prefix sum
            prefix_count[curr_sum] += 1
 
            # Explore children
            dfs(node.left, curr_sum)
            dfs(node.right, curr_sum)
 
            # Backtrack: remove current prefix sum
            prefix_count[curr_sum] -= 1
 
        dfs(root, 0)
        return self.result

var pathSum = function(root, targetSum) {
    const prefixCount = new Map();
    prefixCount.set(0, 1);  // empty path prefix
    let result = 0;
 
    function dfs(node, currSum) {
        if (!node) return;
 
        currSum += node.val;
 
        // Valid paths ending at this node
        result += prefixCount.get(currSum - targetSum) || 0;
 
        // Record current prefix sum
        prefixCount.set(currSum, (prefixCount.get(currSum) || 0) + 1);
 
        dfs(node.left, currSum);
        dfs(node.right, currSum);
 
        // Backtrack
        prefixCount.set(currSum, prefixCount.get(currSum) - 1);
    }
 
    dfs(root, 0);
    return result;
};

Time: O(n) — each node visited exactly once Space: O(n) — hashmap stores at most O(h) entries at any time, O(n) worst case for skewed tree

Common Mistakes#

• Forgetting to initialize prefix_count[0] = 1 — this handles paths that start from the root itself
• Skipping the backtracking step, causing prefix sums from one branch to pollute sibling branches
• Using a global running sum without resetting — the running sum is passed by value in the recursion, so it resets naturally
• Confusing path direction — paths must go downward (parent to child), not arbitrarily
• Integer overflow on large trees — use 64-bit integers when node values can be up to 10^9

Interview Tips#

• Always draw the connection to "subarray sum equals k" — it shows pattern recognition
• Explicitly state why backtracking is needed before writing the code
• Mention the naive O(n^2) approach first, then explain why prefix sums improve it to O(n)
• The prefix_count[0] = 1 initialization is a subtle point interviewers look for — explain it clearly

Follow-up Questions#

• What if paths can go through the root in any direction (up and down)? This becomes LC 124 (Binary Tree Maximum Path Sum) territory — use a global max and return only one direction per node.
• What if you need to return the actual paths, not just the count? Track the current path in a list and record it whenever a valid path is found.
• How does this change for an n-ary tree? The same DFS + prefix sum approach works — just iterate over all children instead of left/right.
• What is the space complexity of the recursive approach vs iterative? Both are O(h) for the call stack; the hashmap adds O(n) worst case.
• Can negative values cause issues? No — the prefix sum approach works correctly with negative values since it tracks exact sums, not just non-negative ones.

Key Takeaways#

• Path Sum III is the tree version of "subarray sum equals k" — both use prefix sums in a hashmap
• A path ending at node X sums to target if prefix[X] - prefix[ancestor] == target
• Initialize prefix_count[0] = 1 to handle paths starting from the root
• Always backtrack (decrement prefix count) after returning from a subtree
• Time complexity is O(n) — each node is visited exactly once
• Space complexity is O(n) for the hashmap; O(h) on the call stack
• The DFS + backtrack + hashmap combo is a powerful pattern applicable to many tree counting problems