Path Sum III
Given the root of a binary tree and a target sum, count the number of paths that sum to the target, where a path only needs to go downward (parent to child) but can start and end at any node.
Open on LeetCode ↗Intuition
The trap is assuming a path has to start at the root, the way it does in Path Sum I and II. Here it can start and end anywhere, as long as it only moves downward -- so a straightforward 'does root-to-here sum to target' check misses every path that starts partway down. The O(n^2) fix is honest but slow: restart a fresh downward sum count at every single node. The O(n) fix reframes the problem as a prefix-sum question, exactly like the array version: track the running sum from the root to the current node, and keep a hashmap counting how many times each prefix sum has occurred on the current root-to-here chain. If runningSum - target is a key in that map, every occurrence marks the start of a valid downward path ending at the current node. The part everyone forgets is that the map has to be scoped to the current path -- after recursing into a node's children, you must decrement (and possibly delete) that node's prefix sum before returning to its parent, or a sibling subtree could wrongly match against a sum left over from a different branch.
Approach
Reframe as prefix sums on a tree path
Treat the root-to-current-node chain like a 1D array and apply the same prefix-sum trick used for subarray sum problems: if two points on the chain have running sums differing by exactly target, the segment between them is a valid path.
Carry a count map down the recursion
Pass the running sum into each recursive call. Before recursing into children, look up running - target in a map of {prefix sum: count}; add however many times it has appeared to the answer. Then record the current running sum in the map (incrementing its count) before descending.
Remove the sum on the way back out
After both children have been explored, decrement the current running sum's count in the map (deleting the key if it drops to zero) before returning. This keeps the map scoped to exactly the ancestors of whatever node is being visited next, so sibling subtrees never see stale sums from each other.
Solution & live demo
Edge cases
Return 0 immediately; there are no nodes to form a path.
The prefix-sum lookup works the same regardless of sign; seed the map with {0: 1} to correctly count paths that start at the root itself.
A single node whose value is 0 forms its own valid path since running - 0 == running matches its own prior prefix; the seeded {0:1} entry and per-node bookkeeping handle this without special-casing.
The count map naturally accumulates multiple entries for the same prefix sum along one path, so overlapping and nested valid paths are all counted correctly.