algoadvance

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

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 tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

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

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Clarifying Questions

  1. Can the sum be negative?
  2. Are all the node values in the tree integers?
  3. Should we consider paths that only consist of a single node?

Strategy

To solve the problem, we’ll use a depth-first search (DFS) and a hash map to store the prefix sums. This approach allows us to efficiently count the number of subarrays (or paths in the context of the tree) that sum up to the target value sum.

Steps:

  1. Use a recursive DFS function to traverse the tree.
  2. Use a hash map to store the cumulative sums of the paths encountered.
  3. At each node, calculate the current path sum.
  4. Check if there has been any previous path sum that when subtracted from the current path sum equals the target sum.
  5. Add the current path sum to the hash map.
  6. Continue to traverse to the left and right children.
  7. Once a node is fully processed, remove its path sum from the hash map to avoid affecting sibling nodes.

Code

from collections import defaultdict

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

def pathSum(root: TreeNode, sum: int) -> int:
    def dfs(node, curr_sum):
        nonlocal count
        if not node:
            return
        
        # Current path sum
        curr_sum += node.val
        
        # Check if there is a prefix sum that satisfies the condition
        count += prefix_sums[curr_sum - sum]
        
        # Update the prefix sums with the current path sum
        prefix_sums[curr_sum] += 1
        
        # Recur for left and right children
        dfs(node.left, curr_sum)
        dfs(node.right, curr_sum)
        
        # Remove the current path sum from the hash map to backtrack
        prefix_sums[curr_sum] -= 1
    
    count = 0
    prefix_sums = defaultdict(int)
    prefix_sums[0] = 1  # Base case: single node path sum == sum
    
    dfs(root, 0)
    return count

Time Complexity

Try our interview co-pilot at AlgoAdvance.com