{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Path Sum III – Solution & Complexity

Interview solutions
/
Path Sum III

Solution Walkthrough

  1. Step 1: Brute-force every possible starting node

    • For each node, count how many downward paths starting exactly there sum to the remaining target.
    • Then recurse into the left and right child as new starting points.
    • This is easy to reason about and correct, but in a skewed tree it revisits many descendants for many different starts, so the worst-case time is O(n^2).
    def path_sum(root: TreeNode, target_sum: int) -> int:
    def count_from(node: TreeNode | None, remaining: int) -> int:
        if node is None:
            return 0

        total = 1 if node.val == remaining else 0
        total += count_from(node.left, remaining - node.val)
        total += count_from(node.right, remaining - node.val)
        return total

    if root is None:
        return 0

    return (
        count_from(root, target_sum)
        + path_sum(root.left, target_sum)
        + path_sum(root.right, target_sum)
    )

  2. Step 2: Use prefix sums plus a hash map for a single DFS

    • Track the running sum from the root to the current node.
    • A path ending at the current node sums to targetSum whenever an earlier prefix sum equals currentSum - targetSum.
    • Store counts of prefix sums in a hash map as you go down the tree, then decrement that count while backtracking so sibling paths do not accidentally reuse state from each other.
    • This counts every valid downward path in O(n) time with O(h) recursion stack plus up to O(n) prefix-sum storage.
    def path_sum(root: TreeNode, target_sum: int) -> int:
    prefix_counts = {0: 1}

    def dfs(node: TreeNode | None, current_sum: int) -> int:
        if node is None:
            return 0

        current_sum += node.val
        total = prefix_counts.get(current_sum - target_sum, 0)

        prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
        total += dfs(node.left, current_sum)
        total += dfs(node.right, current_sum)
        prefix_counts[current_sum] -= 1

        return total

    return dfs(root, 0)

FAQ

See also

Practice Path Sum III online (run code in the browser)Balanced Binary Tree solution (easy)Binary Tree Inorder Traversal solution (easy)Binary Tree Maximum Path Sum solution (hard)Binary Tree Postorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?