Path Sum III
Problem
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 (traveling only from parent nodes to child nodes).
- The number of nodes in the tree is in the range [0, 1000]
- −10⁹ ≤ Node.val ≤ 10⁹
- −1000 ≤ targetSum ≤ 1000
Example
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 83The paths that sum to 8 are: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11 The algorithm uses a prefix sum map to track cumulative sums from the root to the current node. At each node, it calculates the current cumulative sum and checks if there exists a prefix sum such that current_sum - prefix_sum = targetSum. This indicates a valid path ending at the current node. The prefix map is updated before exploring children and restored after to maintain correct counts for sibling branches.
Approach
Straightforward Solution
A naive approach would explore all paths starting from every node, resulting in O(n^2) time complexity, which is inefficient for large trees.
Core Observation
The problem reduces to finding the number of sub-paths in a root-to-current-node path whose sums equal targetSum. Using prefix sums, the difference between two prefix sums equals the sum of the nodes in between, enabling O(1) checks for valid paths ending at the current node.
Path to Optimal
The key insight is to use a prefix sum map that records how many times a particular cumulative sum has occurred along the current path. At each node, the algorithm calculates the current cumulative sum and checks if (current_sum - targetSum) exists in the map, indicating a valid path. This transforms the problem into a DFS with prefix sum bookkeeping, reducing redundant computations.
Optimal Approach
Perform a DFS traversal, maintaining a prefix sum map that counts occurrences of cumulative sums along the current path. For each node, update the current sum, check for valid paths using the map, recurse into children, and then backtrack by decrementing the count of the current sum. This ensures correct counting of paths and avoids double counting across different branches.
Time
O(n)
Each node is visited once in the DFS traversal. Prefix sum map operations (get, set) are O(1) on average, resulting in overall linear time.
Space
O(n)
The prefix sum map stores counts of cumulative sums along the current path, which can be up to the height of the tree (O(n) in worst case). The recursion stack also uses O(n) space in the worst case.
Pattern Spotlight
DFS (Prefix Sum with Backtracking)
When counting paths with a target sum in a tree, use prefix sums to convert the problem into counting subarrays with a given sum along root-to-node paths, and carefully backtrack prefix counts to maintain correctness across branches.
Solution
| 1 | class Solution: |
| 2 | def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: |
| 3 | prefix = {0: 1} |
| 4 | |
| 5 | def dfs(node, curr_sum): |
| 6 | if not node: |
| 7 | return 0 |
| 8 | |
| 9 | curr_sum += node.val |
| 10 | count = prefix.get(curr_sum - targetSum, 0) |
| 11 | |
| 12 | prefix[curr_sum] = prefix.get(curr_sum, 0) + 1 |
| 13 | |
| 14 | count += dfs(node.left, curr_sum) |
| 15 | count += dfs(node.right, curr_sum) |
| 16 | |
| 17 | prefix[curr_sum] -= 1 |
| 18 | |
| 19 | return count |
| 20 | |
| 21 | return dfs(root, 0) |
Step-by-Step Solution
Initialize Prefix Sum Map to Track Cumulative Sums
| 3 | prefix = {0: 1} |
Objective
To create a dictionary that maps cumulative sums to their frequency along the current traversal path.
Key Insight
Starting with prefix sum 0 occurring once accounts for paths that start at the root and sum exactly to targetSum. This initialization is critical to correctly count paths that begin at the root node without requiring special case handling.
Interview Quick-Check
Core Logic
The prefix map stores cumulative sums and their counts, enabling O(1) checks for valid sub-path sums ending at the current node.
Common Pitfalls & Bugs
Failing to initialize prefix[0] = 1 causes missing valid paths that start at the root.
Traverse Tree with DFS While Updating and Backtracking Prefix Sums
| 5 | def dfs(node, curr_sum): |
| 6 | if not node: |
| 7 | return 0 |
| 9 | curr_sum += node.val |
| 10 | count = prefix.get(curr_sum - targetSum, 0) |
| 12 | prefix[curr_sum] = prefix.get(curr_sum, 0) + 1 |
| 14 | count += dfs(node.left, curr_sum) |
| 15 | count += dfs(node.right, curr_sum) |
| 17 | prefix[curr_sum] -= 1 |
| 19 | return count |
Objective
To recursively explore each node, update the current cumulative sum, count valid paths, and backtrack prefix sums to maintain correct state.
Key Insight
At each node, the algorithm calculates the cumulative sum and uses the prefix map to find how many prefix sums satisfy the condition for a valid path. Incrementing the prefix count before recursion and decrementing after ensures that sibling branches do not interfere with each other's prefix sums, preserving correctness.
Interview Quick-Check
Core Logic
The DFS updates the prefix map with the current sum before exploring children and decrements it after, ensuring accurate path counts without double counting.
State & Boundaries
The base case returns 0 when reaching a null node, terminating recursion.
Common Pitfalls & Bugs
Neglecting to decrement prefix counts after recursion leads to incorrect path counts due to shared state across branches.
Return Total Count of Valid Paths from DFS
| 21 | return dfs(root, 0) |
Objective
To return the total number of valid paths found starting from the root node.
Key Insight
The initial call to dfs with the root and cumulative sum 0 triggers the entire traversal and counting process, returning the final answer.
Interview Quick-Check
Core Logic
The final return aggregates all valid paths found in the tree.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
count = prefix.get(curr_sum - targetSum, 0)Count paths ending at current node with sum equal to targetSum.
By checking prefix sums for (curr_sum - targetSum), the algorithm identifies how many valid sub-paths end at this node, enabling O(1) counting of valid paths.
prefix[curr_sum] -= 1Decrement count of current cumulative sum to backtrack.
Backtracking the prefix map count after visiting children prevents sibling branches from incorrectly sharing prefix sums, preserving correctness.
prefix[curr_sum] = prefix.get(curr_sum, 0) + 1Increment count of current cumulative sum in prefix map.
Updating the prefix map before recursion ensures that child nodes can correctly identify valid paths that include the current node.
prefix = {0: 1}Initialize prefix sum map with 0 sum occurring once.
This initialization accounts for paths that start at the root and sum exactly to targetSum, enabling correct counting without special cases.
curr_sum += node.valAdd current node's value to cumulative sum.
Updating the cumulative sum at each node is essential to track the sum of the path from the root to the current node.
return countReturn total count of valid paths found at this node and its subtrees.
Aggregates counts from current node and its descendants, enabling the recursive accumulation of the final answer.
return dfs(root, 0)Start DFS traversal from root with initial sum 0 and return total count.
This call triggers the entire prefix sum DFS process, returning the total number of valid paths in the tree.
if not node:Return 0 if the current node is null (base case).
This base case terminates recursion when leaf nodes are reached, preventing null pointer errors and signaling no paths from this branch.
count += dfs(node.left, curr_sum)Recursively count valid paths in left subtree.
Exploring the left subtree accumulates counts of valid paths that include nodes in that branch.
count += dfs(node.right, curr_sum)Recursively count valid paths in right subtree.
Exploring the right subtree accumulates counts of valid paths that include nodes in that branch.
def dfs(node, curr_sum):Define the recursive DFS helper function with current node and cumulative sum.
Encapsulating the traversal and prefix sum logic in a helper function allows clean recursion and state management.
return 0Return 0 immediately for null nodes.
Ensures that null nodes contribute no paths, maintaining correctness of the count aggregation.
Test Your Understanding
Why must the prefix sum count be decremented after visiting both children of a node?
Because the prefix sum map tracks cumulative sums along the current path only. Decrementing after visiting children backtracks the state to avoid counting paths from sibling branches that do not share the current node's prefix sums.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Path Sum III from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Path Sum III drill