We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Path Sum III

Number: 437

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg, Salesforce, Meta, Microsoft, Adobe, Flipkart, TikTok, Apple

Problem Description

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

Key Insights

  • A path can start and end at any nodes, as long as it goes downwards.
  • Using DFS helps traverse the tree and explore all possible paths.
  • A prefix sum technique with a hash map allows quick calculation of the sum of any subpath.
  • Backtracking is used to remove a path's prefix sum when moving back up the recursion tree.
  • Although a brute-force approach exists, it is inefficient compared to the prefix sum method.

Space and Time Complexity

Time Complexity: O(n) on average (where n is the number of nodes), though worst-case can be O(n^2) in a skewed tree. Space Complexity: O(n) due to recursion stack and the hash map that stores prefix sums.

Solution

The solution employs a DFS traversal of the tree along with a hash map that records the frequency of prefix sums encountered so far. At each node, the current prefix sum is updated by adding the node’s value. We then check the hash map for how many times (current prefix sum - targetSum) has occurred, since this value indicates the existence of a subpath summing to targetSum. We update the hash map with the current prefix sum, continue the DFS to traverse child nodes, and then backtrack by decrementing the current prefix sum's count before retreating to the parent node. This ensures that sums from other branches are not incorrectly combined.

Code Solutions

# Python solution for Path Sum III
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val            # value of the node
        self.left = left          # left child
        self.right = right        # right child

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        # Helper function to perform DFS traversal
        def dfs(node, current_sum, prefix_sums):
            if not node:
                return 0

            # Update current sum by including the current node's value
            current_sum += node.val
            # Check the number of times (current_sum - targetSum) has occurred
            num_paths = prefix_sums.get(current_sum - targetSum, 0)

            # Update the prefix sum hash map with the current sum
            prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1

            # Recursively search in the left and right subtree
            num_paths += dfs(node.left, current_sum, prefix_sums)
            num_paths += dfs(node.right, current_sum, prefix_sums)

            # Backtrack: remove the current sum count before returning to the parent node
            prefix_sums[current_sum] -= 1
            return num_paths

        # Initial prefix sum hashmap with 0 sum seen once (empty path)
        prefix_sums = {0: 1}
        return dfs(root, 0, prefix_sums)
← Back to All Questions