DSA problem
Path Sum III
Given the root of a binary tree and an integer targetSum, return the number of downward paths in the tree whose node values sum to targetSum. A downward path is any sequence of consecutive parent-to-child nodes — it does not have to start at the root or end at a leaf, but it must travel only downward.
The brute-force solution starts a fresh path-sum search at every node and tries to find continuations whose sum equals the target. That costs O(n²) in a balanced tree and O(n²) on average for a skewed tree, which is sometimes acceptable but rarely interesting.
The optimal approach borrows the classic prefix-sum hashmap trick from the 1-D "subarray sum equals K" problem. Treat the path from the root to the current node as a 1-D array of values, and maintain currSum = sum from the root to the current node. A downward path ending at the current node has sum targetSum iff there is some ancestor along that path whose root-to-ancestor sum is currSum - targetSum. So we keep a hash map from running prefix sum → frequency along the current root-to-node path; at every node we add freq[currSum - targetSum] to the answer, then bump freq[currSum], recurse, and decrement freq[currSum] on the way out so siblings do not see this contribution.
Use a 64-bit integer for currSum: with values as large as 10^9 and trees of up to 1000 nodes, partial sums can overflow a 32-bit int. The complexity is O(n) time and O(h) space — a one-pass preorder DFS, exactly the canonical pattern.
Examples
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 83root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 223root = [1,-2,-3], targetSum = -12Constraints
- The number of nodes in the tree is in the range [0, 1000].
- -10^9 <= Node.val <= 10^9
- -1000 <= targetSum <= 1000
- Use a 64-bit integer for the running prefix sum to avoid overflow.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.