437. Path Sum III

Introduction

The "Path Sum III" problem involves finding the number of paths in a binary tree where the sum of the values along the path equals a given target sum. The path can start and end at any node, but it must go downwards, meaning it must travel from parent to child nodes. This problem is typically solved using depth-first search (DFS) and can benefit from using a hashmap (or dictionary) to store the cumulative sum of paths as we traverse the tree.

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

        class TreeNode:
            def __init__(self, val=0, left=None, right=None):
                self.val = val
                self.left = left
                self.right = right
        

The tree node structure is given above. The goal is to count how many paths sum to `targetSum`.

Approach

To solve this problem, we use a depth-first search (DFS) approach combined with a hashmap to track the cumulative sums along the paths. The key insight is that we can compute the number of valid paths by maintaining a running sum and using the hashmap to check how many times a particular sum has occurred in the past. Specifically, for each node, we check if there exists a previous cumulative sum such that the difference between the current sum and the target sum equals this previous sum.

• Start by performing a DFS traversal of the tree.
• At each node, calculate the cumulative sum along the path from the root to the current node.
• Use a hashmap to track how many times each cumulative sum has occurred so far. If the difference between the current cumulative sum and the target sum exists in the hashmap, it means there is a valid path that sums to the target sum.
• Recursively apply the same logic to both the left and right children of the current node.

Algorithm

The algorithm follows these steps:

1. Define a helper function that performs a DFS traversal while maintaining the current path sum.
2. At each node, update the current path sum and check if the difference between the current path sum and `targetSum` exists in the hashmap.
3. Recursively call the helper function for both the left and right children of the current node.
4. Update the hashmap at each step and backtrack when necessary to remove the current node’s path sum.

By leveraging a hashmap to track the cumulative sums, we efficiently compute the number of paths that sum to the target value.

Example

Consider the following binary tree and a target sum of 8:

            10
           /  \
          5   -3
         / \    \
        3   2   11
       / \    /  \
      3  -2  1    5
        

For this tree, the following paths sum to 8: - Path 1: 5 → 3 (sum = 8) - Path 2: 5 → 3 → 2 → 1 (sum = 8) - Path 3: 10 → -3 → 11 (sum = 8)

Thus, there are 3 valid paths that sum to 8 in this tree.

Code Implementation

Below is the Python implementation of the algorithm to count the number of paths that sum to the target value in a binary tree:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pathSum(root, targetSum):
    def dfs(node, current_sum, prefix_sum):
        if not node:
            return 0
        
        # Update the current path sum
        current_sum += node.val
        count = prefix_sum.get(current_sum - targetSum, 0)
        
        # Add the current path sum to the prefix sum map
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
        
        # Recursively count paths in the left and right subtrees
        count += dfs(node.left, current_sum, prefix_sum)
        count += dfs(node.right, current_sum, prefix_sum)
        
        # Backtrack: remove the current path sum from the prefix sum map
        prefix_sum[current_sum] -= 1
        
        return count

    # Initialize the prefix sum map with 0 sum having one occurrence
    prefix_sum = {0: 1}
    return dfs(root, 0, prefix_sum)
        

In this code: - The `dfs` function performs the DFS traversal and maintains the running sum of the path from the root to the current node. - The `prefix_sum` dictionary stores how many times each cumulative sum has been encountered so far. - If the difference between the current path sum and the target sum exists in the `prefix_sum` map, it means that there is a path whose sum equals the target sum. - We backtrack after visiting the left and right children to ensure we do not count the same path multiple times.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. Each node is visited once, and for each node, checking the prefix sum in the hashmap takes O(1) time. Therefore, the overall time complexity is linear in terms of the number of nodes.

The space complexity is O(n), where n is the number of nodes in the tree. This accounts for the recursion stack and the space used by the `prefix_sum` hashmap, which can store up to O(n) different sums in the worst case.

Conclusion

The "Path Sum III" problem is a classic problem in binary trees that can be efficiently solved using depth-first search (DFS) combined with a hashmap. By maintaining a running sum and using the hashmap to track how many times a particular sum has occurred, we can quickly determine how many paths sum to the target value. This problem helps strengthen skills in tree traversal and dynamic sum tracking.