How do you solve Path Sum III?

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.

What pattern does Path Sum III use?

The Pattern: DFS (Prefix Sum with Backtracking) The Heuristic: 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.

Path Sum III — DFS

Q: What is the time complexity of Path Sum III?

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.

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

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

Output: 3

The 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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Perform a DFS traversal, maintaining a prefix sum map that counts occurrences of cumulative sums along the current path…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Solution

Python

1class 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

1

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.

2

Traverse Tree with DFS While Updating and Backtracking Prefix Sums

To recursively explore each node, update the current cumulative sum, count valid paths, and backtrack prefix sums to maintain correct state.

3

Return Total Count of Valid Paths from DFS

To return the total number of valid paths found starting from the root node.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 10 Critical

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.

Line 17 Critical

prefix[curr_sum] -= 1

Decrement 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.

Line 12 Critical

prefix[curr_sum] = prefix.get(curr_sum, 0) + 1

Increment 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.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why must the prefix sum count be decremented after visiting both children of a node?

See the answer with Pro.

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

or drill a free problem

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)`