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 <= 1000Problem Overview: You are given the root of a binary tree and a target sum. Count the number of paths where the sum of node values equals the target. A valid path must move downward (parent to child) but can start and end at any node in the tree.
Approach 1: Depth-First Search with Path Sum Calculation (Time: O(n^2), Space: O(h))
This approach treats every node as a potential starting point of a path. From each node, run a Depth-First Search that keeps subtracting the current node value from the remaining target. If the remaining value becomes zero, you found a valid path. After finishing paths starting from one node, recursively repeat the process for its left and right children.
The key idea is straightforward: explore every downward path starting at every node. In the worst case (a skewed tree), each DFS may traverse most of the tree, giving O(n^2) time complexity. Space complexity is O(h) for the recursion stack, where h is the tree height. This approach is simple to implement and works well for smaller trees, making it a good baseline solution when working with tree traversal problems.
Approach 2: Prefix Sum with Hash Map (Time: O(n), Space: O(n))
This optimized solution borrows the prefix sum idea commonly used in arrays and adapts it to a binary tree. While traversing the tree with DFS, maintain the running sum from the root to the current node. If the current prefix sum is curr and there was a previous prefix sum curr - target, then the nodes between them form a path that equals the target.
A hash map stores how many times each prefix sum has appeared along the current traversal path. Before exploring children, update the map with the current prefix sum. When backtracking, decrement the count so sibling branches do not reuse the same prefix path. Each node is processed once, and hash lookups take constant time, resulting in O(n) time and O(n) extra space.
Recommended for interviews: Start by explaining the DFS-from-every-node approach since it demonstrates clear understanding of tree traversal. Then move to the prefix sum optimization. Interviewers typically expect the O(n) prefix sum solution because it shows you can adapt array techniques to tree structures and manage state correctly during recursion.
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
This 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
Time Complexity: O(n^2) in the worst case. Space Complexity: O(n) due to the function call stack.
This approach leverages a hashmap to store cumulative sums and uses them to find paths that lead to the targetSum.
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.
Time Complexity: O(n). Space Complexity: O(n), where n is the number of nodes in the tree.
We can use the idea of prefix sums to recursively traverse the binary tree while using a hash table cnt to count the occurrences of each prefix sum along the path from the root to the current node.
We design a recursive function dfs(node, s), where node represents the current node being traversed, and s represents the prefix sum along the path from the root to the current node. The return value of the function is the number of paths ending at node or its subtree nodes with a sum equal to targetSum. The final answer is dfs(root, 0).
The recursive process of dfs(node, s) is as follows:
node is null, return 0.s along the path from the root to the current node.cnt[s - targetSum] to represent the number of paths ending at the current node with a sum equal to targetSum. Here, cnt[s - targetSum] is the count of prefix sums equal to s - targetSum in cnt.s by 1, i.e., cnt[s] = cnt[s] + 1.dfs(node.left, s) and dfs(node.right, s), and add their return values.s by 1, i.e., cnt[s] = cnt[s] - 1.The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Using Depth-First Search (DFS) and Path Sum Calculation | Time Complexity: O(n^2) in the worst case. Space Complexity: O(n) due to the function call stack. |
| Using Hashmap to Store Prefix Sums | Time Complexity: O(n). Space Complexity: O(n), where n is the number of nodes in the tree. |
| Hash Table + Prefix Sum + Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS from Every Node | O(n^2) | O(h) | Simple implementation or when explaining baseline reasoning in interviews |
| Prefix Sum with Hash Map | O(n) | O(n) | Best general solution; expected in interviews for optimal performance |
Path Sum iii | LeetCode 437 | C++, Java, Python • Knowledge Center • 48,967 views views
Watch 9 more video solutions →Practice Path Sum III with our built-in code editor and test cases.
Practice on FleetCode