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.
1#include <stdio.h>
2#include <stdbool.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10int pathSumFrom(struct TreeNode* node, int targetSum) {
11 if (!node) return 0;
12 return (node->val == targetSum) +
13 pathSumFrom(node->left, targetSum - node->val) +
14 pathSumFrom(node->right, targetSum - node->val);
15}
16
17int pathSum(struct TreeNode* root, int targetSum) {
18 if (!root) return 0;
19 return pathSumFrom(root, targetSum) +
20 pathSum(root->left, targetSum) +
21 pathSum(root->right, targetSum);
22}
23This recursive solution calculates the number of paths that sum to the targetSum starting from each node. The function pathSumFrom checks both left and right paths recursively
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.
The Java solution maintains a hashmap to track cumulative sums up to each node. The method helper explores the tree recursively, adjusting entries in the hashmap as nodes are visited and backtracking appropriately.