Path Sum III — InterviewPrepKit

Solving tips

Recognize this as the tree version of 'count subarrays summing to k' (LeetCode 560): a root-to-node path is a prefix sum.
DFS carrying the running root-to-here sum and a hash map count[prefix]; at each node add count[running - targetSum] to the answer for O(n) time, O(n) space.
Seed count[0] = 1 so paths starting at the root are counted.
Pitfall: decrement count[running] when backtracking, or prefixes from one subtree leak into the sibling and overcount; don't early-return on hitting the target since negatives let a longer path hit it again.

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

Hint 1

Every downward path is described by two nodes: where it starts and where it ends. What if you fix the starting node and search downward from it?

Hint 2

In arrays, "count subarrays summing to k" is solved with prefix sums and a hash map: a subarray sums to k exactly when two prefixes differ by k. A root-to-node path is a prefix here.

Hint 3

DFS while carrying the running root-to-current sum and a hash map counting how often each prefix sum occurred on the current root path. At each node, add `count[current - targetSum]` to the answer — and decrement the node's own entry when backtracking so counts never leak across branches.

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 somewhere. So: for each node in the tree, run a second DFS downward from it, extending the running sum and counting every time it hits targetSum. (Don’t stop at the first hit — negatives mean the sum can return 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

class Solution:
    def pathSum(self, 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)
                + self.pathSum(root.left, targetSum)
                + self.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)

The insight: 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’s child… down to b sums to targetSum exactly when prefix(b) - prefix(a) = targetSum, i.e. when some ancestor prefix equals prefix(b) - targetSum. So 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 subtlety unique to trees: when the DFS leaves a node, its prefix must be removed from the map, or a prefix from the left subtree would be visible while exploring the right subtree — and left-branch prefixes are not ancestors of right-branch nodes.

# 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

class Solution:
    def pathSum(self, 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}.

Node 1: running = 1. Need 1 - 0 = 1 → count is 0 hits. Map {0:1, 1:1}.
Node -1: running = 0. Need 0 → map has 1 → one path found (1 → -1). Map {0:2, 1:1}.
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}.
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), grafted onto a DFS with backtracking.

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.