Path Sum III
Last Updated: April 1, 2026
Understanding the Problem
This problem is a twist on the classic Path Sum problems. In Path Sum I and II, paths had to start at the root and end at a leaf. Here, the rules are much looser: a valid path can start at any node and end at any node below it. The only constraint is that the path must go downward, following parent-to-child edges.
This changes things significantly. Consider a tree where nodes along a root-to-leaf route have values [10, 5, 3, -2]. The subpath [5, 3] sums to 8, and it starts in the middle of the tree. We need to count paths like that.
The key observation is that any valid path is a contiguous subpath of some root-to-node path. If we think of the values along a root-to-node route as an array, we're essentially asking: how many contiguous subarrays sum to the target? That reframing connects this tree problem to the well-known "subarray sum equals K" problem, and that's where the prefix sum technique comes in.
Key Constraints:
Number of nodes up to 1000→ This is a small tree. Even O(n^2) approaches will pass easily. But learning the O(n) technique is valuable for interviews and larger inputs.-10^9 <= Node.val <= 10^9→ Node values can be very large (positive or negative). We need to uselongin languages like Java/C++ to avoid integer overflow when computing prefix sums.-1000 <= targetSum <= 1000→ The target can be negative, so we can't make assumptions about path sums being positive.
Approach 1: Brute Force (DFS from Every Node)
Intuition
The most straightforward idea: treat every node as a potential starting point for a path, then walk downward from that node and count how many paths hit the target sum. Since valid paths must go downward, from any starting node we just do a DFS and keep a running sum. Whenever the running sum equals targetSum, we've found a valid path.
We need two layers of recursion here. The outer layer visits every node in the tree (to try it as a starting point). The inner layer, starting from a given node, explores all downward paths and counts the ones that sum to the target.
Algorithm
- Traverse the entire tree using DFS. At each node, call a helper function that counts paths starting from that node.
- In the helper function, maintain a running sum. Add the current node's value to it.
- If the running sum equals
targetSum, increment the count. - Recurse into the left and right children, carrying the running sum forward.
- The total count is the sum of valid paths found from every starting node.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n nodes, we potentially traverse down to every node below it. In a skewed tree, the outer DFS visits n nodes and the inner DFS from each node visits up to n nodes, summing to O(n^2). In a balanced tree, this is O(n log n).
- Space Complexity: O(n). The recursion stack can go up to O(n) deep in a skewed tree. In a balanced tree it's O(log n).
This works, but for every node we re-traverse large portions of the tree. What if we could compute running sums from the root just once and use a data structure to instantly check whether any earlier prefix sum, when subtracted, gives us the target?
Approach 2: Prefix Sum with Hash Map (Optimal)
Intuition
Here's the key insight that transforms this from a tree problem into something we've seen before. Consider any path from the root to the current node. The values along that path form an array. A valid path that ends at the current node is just a contiguous subarray of that root-to-node array that sums to targetSum.
Now, how do we efficiently find contiguous subarrays with a given sum? This is the classic "subarray sum equals K" technique. If the prefix sum from the root to the current node is currentSum, and at some ancestor the prefix sum was currentSum - targetSum, then the path between that ancestor and the current node sums to exactly targetSum.
So we maintain a hash map that counts how many times each prefix sum has appeared on the current root-to-node path. At each node, we check how many ancestors had a prefix sum of currentSum - targetSum. That count tells us exactly how many valid paths end at this node.
The tricky part is backtracking. When we finish processing a subtree and move to a sibling branch, the prefix sums from the finished subtree shouldn't be in our map anymore. So after exploring both children of a node, we decrement that node's prefix sum count in the map. This keeps the map accurate for only the current root-to-node path.
The prefix sum trick works because of a simple mathematical identity. If the prefix sum from root to node A is P_A and the prefix sum from root to node B (a descendant of A) is P_B, then the path sum from A to B is P_B - P_A. So if we want P_B - P_A = targetSum, we need P_A = P_B - targetSum. The hash map tells us instantly how many such ancestors exist.
The backtracking step is crucial. Without it, prefix sums from one branch would leak into another. Imagine two sibling subtrees, both passing through prefix sum 15. If we don't remove the first subtree's prefix sum 15 from the map before exploring the second subtree, we'd falsely match against it and overcount.
Algorithm
- Initialize a hash map with
{0: 1}. This handles the case where a path from the root itself sums to the target. - DFS through the tree, maintaining a running
currentSumfrom the root. - At each node, add
node.valtocurrentSum. - Check the map for
currentSum - targetSum. The count stored there is the number of valid paths ending at this node. - Add
currentSumto the map (increment its count). - Recurse into the left and right children.
- After both children are processed, remove
currentSumfrom the map (decrement its count). This is the backtracking step.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once during the DFS. At each node, the hash map lookup and update are O(1) on average.
- Space Complexity: O(n). The hash map stores at most one entry per node on the current root-to-node path, which is O(h) where h is the tree height. The recursion stack is also O(h). In the worst case (skewed tree), h = n.