< Back




437. Path Sum III

We're asked to return the number of paths in a binary tree that size to a target sum. The path
doesn't have to start at the root or end at a leaft, making this problem a bit harder. To solve
this, we use a prefix sum to track the number of times we see a particular sum. This allows us to
essentially reset the sum at any point in the tree, so when the prefix sum is equal to the target
again, we have an accurate count.

When we backtrack to a node, we remmove the prefix sum from the hashmap, so we don't count it in
other paths.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
          self.ans = 0
          h = defaultdict(int)

          def dfs(node: Optional[TreeNode], currSum: int) -> None:
              if not node:
                  return

              currSum += node.val

              if currSum == targetSum:
                  self.ans += 1

              self.ans += h[currSum - targetSum]

              h[currSum] += 1
              dfs(node.left, currSum)
              dfs(node.right, currSum)
              h[currSum] -= 1

          dfs(root, 0)
          return self.ans


_ Time Complexity:

  O(n) - We traverse O(n) nodes of the tree.

_ Space Complexity:

  O(n) - We maintain a hashmap of size O(n).