Path Sum III
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. 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.
Any valid path is a contiguous subpath of some root-to-node path. If we treat the values along a root-to-node route as an array, the question becomes: how many contiguous subarrays sum to the target? That reframing connects this tree problem to the "subarray sum equals K" problem, which the prefix sum technique solves.
Key Constraints:
Number of nodes up to 1000→ This is a small tree, so an O(n^2) approach passes. The O(n) technique still matters for larger inputs.-10^9 <= Node.val <= 10^9→ A root-to-node path of up to 1000 nodes, each near 10^9, can produce a prefix sum around 10^12, which overflows a 32-bit int. We use a 64-bit type (longin Java/C#,long longin C++,i64in Rust,int64in Go) for the running sum.-1000 <= targetSum <= 1000→ The target can be negative, so path sums are not guaranteed to grow monotonically. We cannot prune a branch just because its running sum already exceeds the target.
Approach 1: Brute Force (DFS from Every Node)
Intuition
Treat every node as a potential starting point for a path, then walk downward from that node and count how many paths reach the target sum. Since valid paths go downward, from any starting node we run a DFS that carries a running sum. Whenever the running sum equals targetSum, that is one valid path.
This uses two layers of recursion. 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).
The redundancy here is that each node gets re-traversed once per ancestor that started a path through it. The next approach computes a single running sum from the root and uses a hash map to check, in constant time, whether subtracting some earlier prefix sum yields the target.
Approach 2: Prefix Sum with Hash Map (Optimal)
Intuition
Consider any path from the root to the current node. The values along that path form an array, and a valid path ending at the current node is a contiguous subarray of that root-to-node array that sums to targetSum. This is the "subarray sum equals K" problem applied to one path at a time.
The prefix-sum identity drives the speedup. If the prefix sum from the root to the current node is currentSum, and some ancestor on this path had a prefix sum of currentSum - targetSum, then the segment 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, the count stored for currentSum - targetSum is the number of valid paths ending at this node.
Backtracking keeps the map honest. When we finish a subtree and move to a sibling branch, the prefix sums recorded inside that subtree must no longer be visible, because a sibling is not a descendant. After exploring both children of a node, we decrement that node's prefix sum count in the map, so the map only ever reflects prefix sums along the current root-to-node path.
A match only counts if P_A = currentSum - targetSum belongs to an ancestor of the current node, not to a node in a sibling subtree. The map cannot distinguish the two on its own, so the decrement on the way back up enforces the constraint structurally: by the time we visit a sibling, every prefix sum recorded inside the first subtree has already been removed.
Without the decrement, two sibling subtrees that both pass through prefix sum 15 would match against each other. The second subtree would treat the first subtree's 15 as an ancestor and overcount paths that do not exist.
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.