LeetCode 437. Path Sum III

Dec 27, 2025

Intuition

Maintain a Hashmap to store prefix_sum: frequency

Base Case: pathSums[0] = 1 to handle the case when path from Root to CurrentNode equals targetSum exactly

DFS Traversal

  1. Add node.val to currSum
  2. check if currSum - targetSum in hashmap if yes add that count to result
  3. Add currSum to hashmap
  4. recurse left and right
  5. Before returning to the parent, remove the current node's sum from hashmap to ensure the other branch doesn't see prefix sum from this branch

Optimal SOlution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        self.count = 0
        # Initialize map with 0:1 to handle paths that equal targetSum exactly from root
        self.prefix_sums = defaultdict(int)
        self.prefix_sums[0] = 1

        def backtrack(node, current_sum):
            if not node:
                return

            # 1. Update the running sum
            current_sum += node.val
            
            # 2. Check if a valid path ends here
            # current_sum - old_sum = targetSum  =>  old_sum = current_sum - targetSum
            self.count += self.prefix_sums[current_sum - targetSum]
            
            # 3. Add current_sum to map so children can use it
            self.prefix_sums[current_sum] += 1
            
            # 4. Explore
            backtrack(node.left, current_sum)
            backtrack(node.right, current_sum)
            
            # 5. BACKTRACK: Remove the current sum before going back up
            # This is critical so the sum doesn't "leak" into other branches
            self.prefix_sums[current_sum] -= 1

        backtrack(root, 0)
        return self.count

Time Complexity

Time Complexity O(N)

Space Complexity O(H)

Steve Jin