Path Sum III: Prefix Sums on a Tree in One DFS
The problem
LeetCode 437: given a binary tree and a target, count the downward paths (parent to child, any start and end node) whose values add up to the target. The brute force starts a new search from every node, which is O(n²) on a skewed tree. Interviewers want O(n).
The idea
It is the same trick as “subarray sum equals k”, applied to the root-to-node path you are currently on. While you walk down, keep a running sum and a hash map from prefix sum to how many times it appears on the current path. At each node, the number of valid paths that end here is count[running - target]. Add the current prefix to the map, recurse into both children, then remove it again on the way back up so sibling branches never see it.
Code (Python)
def pathSum(root, target):
count = {0: 1}
def dfs(node, running):
if not node:
return 0
running += node.val
found = count.get(running - target, 0)
count[running] = count.get(running, 0) + 1
found += dfs(node.left, running) + dfs(node.right, running)
count[running] -= 1
return found
return dfs(root, 0)
What to say out loud
Seed the map with {0: 1} so a path that starts at the root counts.
2. Look up before you insert, otherwise a target of 0 counts the empty path.
3. The undo step (count[running] -= 1) is the backtracking that keeps the map equal to “prefixes on this path only”.
4. Time O(n), space O(h) for recursion plus O(h) map entries.
Common follow-ups
- Return the paths, not just the count: store lists of depths per prefix instead of counts.
- Values can be negative: the method still works, which is why a sliding window does not.
If you want to rehearse explaining patterns like this under time pressure, Linkjob AI’s coding interview copilot can help you practice.
Disclosure: I work on Linkjob AI.