{x}
blog image

Path Sum III

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

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

 

Constraints:

  • The number of nodes in the tree is in the range [0, 1000].
  • -109 <= Node.val <= 109
  • -1000 <= targetSum <= 1000

Solution Explanation for LeetCode 437: Path Sum III

This problem asks us to find the number of paths in a binary tree where the sum of the nodes along each path equals a given targetSum. The paths don't need to start or end at the root or a leaf, only going downwards.

The most efficient approach uses a depth-first search (DFS) combined with a hash map (dictionary in Python) to count path sums. The hash map stores the prefix sums encountered during the traversal.

Algorithm

  1. Prefix Sum and Hash Map: We utilize a hash map (cnt in the code) to store the frequency of prefix sums encountered so far. The key is the prefix sum, and the value is its count. We initialize the map with 0: 1 because an empty path has a sum of 0.

  2. Depth-First Search (DFS): A recursive DFS function (dfs) traverses the tree. For each node:

    • It adds the node's value to the current prefix sum s.
    • It checks if s - targetSum exists as a key in the hash map. If it does, it means there's a path ending at the current node with the target sum. The value associated with s - targetSum represents the number of such paths. This is added to the ans (count of paths).
    • It updates the frequency count of the current prefix sum s in the hash map.
    • It recursively calls dfs for the left and right children.
    • Finally, it decrements the frequency count of s to backtrack correctly (important for correctly handling overlapping paths).

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited once during the DFS traversal. The hash map operations (insertion, lookup, deletion) take O(1) on average.

  • Space Complexity: O(H), where H is the height of the tree. The space is primarily used by the recursive call stack during DFS. In the worst case (a skewed tree), H can be equal to N. The hash map's space usage depends on the number of distinct prefix sums, which is also at most N in the worst case. Therefore, we can consider the space complexity to be O(N) in the worst case, although it's often much less in practice.

Code Examples (Multiple Languages)

The code examples provided in the problem description demonstrate the algorithm effectively across multiple programming languages. Each example follows the same fundamental logic: DFS traversal combined with prefix sum tracking using a hash map. Key features include:

  • Efficient Hash Map Usage: The hash map ensures quick lookups to determine whether a path with the targetSum exists.
  • Recursive DFS: The recursive nature of DFS elegantly traverses the tree's structure.
  • Backtracking (Decrementing Counts): Decrementing the count of s after the recursive calls is crucial for handling paths that share prefixes correctly.

The choice of language doesn't affect the algorithm's core efficiency; only the specific syntax and data structures vary. The time and space complexities remain the same.