MediumTreeDepth-First SearchBinary Tree

Path Sum III

1 approach, code in every language

You are given the root of a binary tree and an integer targetSum. Count the number of paths whose node values add up to targetSum.

The path does not have to start at the root or end at a leaf, but it must travel strictly downward: it always moves from a parent node to one of its children. Two paths are considered different if they cover a different set of nodes.

Return the total count of such downward paths.

Example 1

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

Output: 3

Three downward paths sum to 8: 5 -> 3, 5 -> 2 -> 1, and -3 -> 11.

Example 2

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

Output: 3

There are three downward paths whose node values total 22.

Constraints

The number of nodes in the tree is in the range [0, 1000].
-10^9 <= Node.val <= 10^9
-1000 <= targetSum <= 1000

Prefix Sums Along the DFS Path

Track running prefix sums from the root to the current node in a hash map, so any qualifying subpath is found in O(1) by looking up prefix - targetSum.

Loading animation…

Intuition

A downward path from an ancestor A to the current node C sums to targetSum exactly when the running total at C minus the running total just above A equals targetSum. That means the number of valid paths ending at C is how many ancestors have a prefix sum equal to currentPrefix - targetSum. We keep a hash map counting how often each prefix sum appears along the current root-to-node chain, seeded with a count of one for the empty prefix zero so that paths starting at the root are counted. As we descend we add the lookup, register our own prefix, recurse, and then decrement our prefix on the way back up so it does not leak into unrelated branches. Because node values can be large, the prefix sums use 64-bit arithmetic to avoid overflow.

Algorithm walkthrough

1Initialize a hash map count with {0: 1}, representing the empty prefix before the root.
2DFS from the root carrying prefix, the sum of values from the root down to the current node.
3At each node add node.val to prefix, then add count[prefix - targetSum] to the answer.
4Increment count[prefix] to make this node's prefix available to its descendants.
5Recurse into both children, then decrement count[prefix] before returning to undo this node's contribution.
6Return the accumulated count of qualifying paths.

Implementation

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        count = {0: 1}
        self.total = 0

        def dfs(node: Optional[TreeNode], prefix: int) -> None:
            if not node:
                return
            prefix += node.val
            self.total += count.get(prefix - targetSum, 0)
            count[prefix] = count.get(prefix, 0) + 1
            dfs(node.left, prefix)
            dfs(node.right, prefix)
            count[prefix] -= 1

        dfs(root, 0)
        return self.total

Time

O(n)

Space

O(n)

Each node is processed once with O(1) expected hash-map operations. The map holds at most one entry per node on the active path, and with the recursion stack the space is O(n) worst case (O(h) for the stack alone). Prefix sums use 64-bit integers to prevent overflow from large node values.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Pipeline Stretch Tallies is our own problem on the technique behind Path Sum III: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free