Path Sum III | Leetcode 437

Welcome to our deep dive on Path Sum III (Leetcode 437). This is an incredibly elegant problem that merges the Prefix Sum technique from Arrays with a classic DFS tree traversal.

Problem Statement

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: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 => Output: 3

Approach: Prefix Sum + DFS Backtracking O(N)

We want to find subarrays (or in this case, a sub-path) that sum to a target. In a flat 1D array, this is solved efficiently in O(N) by tracking a running current_sum and storing its frequencies in a Prefix Sum HashMap. If current_sum - targetSum exists in our HashMap, it strictly means there is a valid sub-path ending exactly at our current node that sums to targetSum!

We can directly map this Array technique to a Tree! The only difference is that trees branch. We must use DFS Backtracking to strictly ensure we only sum paths on a single vertical branch.

1. When we enter a node, we add its value to our running prefix sum.
2. We check if current_sum - targetSum exists in our global HashMap and add that occurrence count to our answer.
3. We increment the frequency of current_sum in our HashMap.
4. We recurse left and right.
5. Backtracking Step: Before we return from the current node's recursion frame, we must remove/decrement current_sum from the HashMap so it doesn't accidentally interfere with an entirely different, parallel branch of the tree!

from collections import defaultdict

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        prefix_sums = defaultdict(int)
        
        # Base case to catch paths that start directly cleanly from the root
        prefix_sums[0] = 1 
        
        def dfs(node, curr_sum):
            if not node:
                return 0
                
            curr_sum += node.val
            
            # Count valid sub-paths ending at the current node
            count = prefix_sums[curr_sum - targetSum]
            
            # Add current sum to our running map
            prefix_sums[curr_sum] += 1
            
            # Recursively search children
            count += dfs(node.left, curr_sum)
            count += dfs(node.right, curr_sum)
            
            # Backtrack optimally by removing this node's sum!
            prefix_sums[curr_sum] -= 1
            
            return count
            
        return dfs(root, 0)

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (437)