Path Sum III

Problem

Given the root of a binary tree and an integer targetSum, count how many downward paths in the tree have values summing to targetSum. A path may start at any node and end at any node below it, but it must go strictly downward (each step parent → child) and contain at least one node. Values may be negative, and the answer counts paths, not nodes.

Examples

• Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 → Output: 3 The qualifying paths are 5 → 3, 5 → 2 → 1, and -3 → 11.
• Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 → Output: 3 Paths: 5 → 4 → 11 → 2, 4 → 11 → 7, and 5 → 8 → 4 → 5.
• Input: root = [1,-1,null,1], targetSum = 0 → Output: 2 In this left-leaning chain 1 → -1 → 1, the paths 1 → -1 and -1 → 1 each sum to 0; the full chain sums to 1 and single nodes don’t qualify.

Constraints

• Up to 1000 nodes; -10^9 <= Node.val <= 10^9; -1000 <= targetSum <= 1000.
• Negative values mean a running sum can revisit earlier totals — no pruning by “sum already too big”.
• O(n²) passes at this size, but the intended solution is O(n).

Think about it first

TL;DR

Prefix-sum hash map carried down a DFS — O(n) time, O(n) space.

Approach 1 — Brute force: try every starting node

Every downward path starts at some node. For each node, run a second DFS downward from it, extending the running sum and counting each time it equals targetSum. Don’t stop at the first hit; negative values can bring the sum back to the target further down.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def pathSum(root: Optional[TreeNode], targetSum: int) -> int:
    def count_from(node: Optional[TreeNode], remaining: int) -> int:
        if not node:
            return 0
        hits = 1 if node.val == remaining else 0
        rest = remaining - node.val
        return (hits
                + count_from(node.left, rest)
                + count_from(node.right, rest))

    if not root:
        return 0
    return (count_from(root, targetSum)
            + pathSum(root.left, targetSum)
            + pathSum(root.right, targetSum))

Complexity: O(n²) time in the worst case (each of n starting nodes scans its whole subtree — think of a skewed chain), O(h) space. With n ≤ 1000 it passes, but it recomputes the same running sums over and over: the path 5 → 2 → 1 is re-summed once for each of its three possible starts.

Approach 2 — Prefix sums on the root path (the classic)

This is the tree version of count subarrays summing to k. Let prefix(v) be the sum of values from the root down to node v. A downward path from a child of a down to b sums to targetSum exactly when prefix(b) - prefix(a) = targetSum, that is, when some ancestor prefix equals prefix(b) - targetSum. DFS down the tree maintaining a hash map count[s] = how many nodes on the current root-to-here path have prefix sum s. At each node, count answers “how many valid paths end here?” in O(1).

The step unique to trees: when the DFS leaves a node, remove its prefix from the map. Otherwise a prefix from the left subtree stays visible while exploring the right subtree, and left-branch prefixes are not ancestors of right-branch nodes. The tree below shows the running prefix at each node in the walkthrough example.

graph TD
    A["node 1<br/>prefix = 1"] --> B["node -1<br/>prefix = 0"]
    B --> C["node 1<br/>prefix = 1"]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import defaultdict

def pathSum(root: Optional[TreeNode], targetSum: int) -> int:
    count: DefaultDict[int, int] = defaultdict(int)
    count[0] = 1  # the empty prefix: paths starting at the root

    def dfs(node: Optional[TreeNode], running: int) -> int:
        if not node:
            return 0
        running += node.val
        paths_ending_here = count[running - targetSum]
        count[running] += 1
        total = (paths_ending_here
                 + dfs(node.left, running)
                 + dfs(node.right, running))
        count[running] -= 1  # backtrack: leave no trace for siblings
        return total

    return dfs(root, 0)

Walkthrough on root = [1,-1,null,1], targetSum = 0 (the left-leaning chain 1 → −1 → 1). Map starts {0: 1}.

1. Node 1: running = 1. Need 1 - 0 = 1 → count is 0 hits. Map {0:1, 1:1}.
2. Node -1: running = 0. Need 0 → map has 1 → one path found (1 → -1). Map {0:2, 1:1}.
3. Node 1: running = 1. Need 1 → map has 1 → one path found (-1 → 1 — the ancestor prefix 1 after the root). Map {0:2, 1:2}.
4. Unwind, decrementing each entry. Total = 2. Matches the expected output.

Complexity: O(n) time — one visit per node with O(1) map work; O(n) space for the map plus O(h) recursion stack (the map holds at most h+1 distinct live counts, but up to n entries transiently on different paths).

This is the classical prefix sum + hash map technique (the array version is LeetCode 560, Subarray Sum Equals K), applied to a DFS that backtracks.

Common pitfalls

• Forgetting count[0] = 1 — paths that start at the root itself are counted by the empty prefix.
• Not decrementing on the way back up: prefixes from one subtree then contaminate the sibling subtree, overcounting.
• Early-returning when the running sum hits the target — with negative values a longer path below can hit it again.
• Sums up to 1000 nodes × 10^9 magnitude overflow 32-bit integers — a real bug in C++/Java; Python’s arbitrary-precision ints hide it, so mention it in an interview anyway.

Pattern takeaway

A root-to-node path is a prefix, so array prefix-sum tricks transfer to trees. Whenever a tree problem asks about contiguous downward segments (count paths with sum k, longest path with property P), carry the running prefix down a DFS and a hash map of ancestor prefixes — and remember the one tree-specific move: undo the map entry when backtracking.