Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
Example 1:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 Output: 3 Explanation: The paths that sum to 8 are shown.
Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: 3
Constraints:
[0, 1000].-109 <= Node.val <= 109-1000 <= targetSum <= 1000Path Sum III asks you to count the number of paths in a binary tree whose values sum to a given target. The path can start and end at any node but must move downward (parent to child).
A straightforward idea is to treat every node as a potential starting point and run a Depth-First Search (DFS) to track cumulative sums along the path. While simple, this method may revisit many nodes repeatedly.
A more efficient strategy uses a prefix sum technique with a hash map. During DFS traversal, maintain the running sum from the root to the current node. If currentSum - target has appeared before, it means a valid path exists ending at the current node. A hash map stores the frequency of prefix sums seen so far, allowing constant-time checks.
This optimized approach processes each node once, leading to O(n) time complexity with additional space used for recursion and prefix tracking.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force DFS from each node | O(n^2) | O(h) |
| Prefix Sum with Hash Map | O(n) | O(n) |
NeetCode
This approach uses a combination of DFS and path sum calculation. For each node, calculate the sum of all paths that end at the current node. This is achieved recursively
Time Complexity: O(n^2) in the worst case. Space Complexity: O(n) due to the function call stack.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6function pathSum(root, targetSum) {
7 if (!root) return 0;
8
9 function pathSumFrom(node, target) {
10 if (!node) return 0;
11 return (node.val === target ? 1 : 0) +
12 pathSumFrom(node.left, target - node.val) +
13 pathSumFrom(node.right, target - node.val);
14 }
15
16 return pathSumFrom(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
17}
18JavaScript implementation that uses recursion to find all paths that sum to the target, analogous to other language solutions with some JavaScript-specific adaptations.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums allow us to track cumulative sums from the root to each node. By checking if the difference between the current sum and the target sum has appeared before, we can quickly identify valid subpaths without re-traversing the tree.
Yes, Path Sum III is a common interview-style problem involving trees, DFS, and prefix sums. Variations of this problem appear in interviews at large tech companies because it tests understanding of tree traversal and hash-based optimization.
The optimal approach uses a prefix sum technique combined with DFS traversal. By storing prefix sums in a hash map, we can determine how many previous paths lead to the required target difference. This reduces the time complexity to O(n) because each node is processed once.
A hash map (or dictionary) is commonly used to store prefix sums and their frequencies during DFS traversal. This allows constant-time checks to determine whether a valid path sum exists ending at the current node.
This solution uses a hashmap called prefix to capture the number of ways to obtain each cumulative sum that ends at a node. When a node is visited, the difference between the current cumulative sum and the target is used to check for matching sums encountered earlier.