← DSA Atlas
Dedicated problem page · #437

Path Sum III

MediumTrees and Binary Search TreesPrefix sum on a root-to-node pathDFS with a running-sum hash map
Solve on LeetCode ↗
437
MediumTrees and Binary Search TreesDFS with a running-sum hash mapPrefix sum on a root-to-node path

Path Sum III

Given the root of a binary tree and an integer targetSum, count the number of downward paths whose node values sum to targetSum. A path must go from a parent to a child (top to bottom) but need not start at the root or end at a leaf.

Open official problem prompt ↗
In plain English

Count how many contiguous top-to-bottom chains of nodes add up to a target value.

Picture it like this

Walking down a trail while noting your total elevation gain at each marker. To find any stretch that gained exactly 8 meters, you check whether some earlier marker was exactly 8 below your current total.

Example
Input
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output
3
Why
The paths 5->3, 5->2->1, and -3->11 each sum to 8.
Constraints
The number of nodes is in the range [0, 1000]-10^9 <= Node.val <= 10^9-1000 <= targetSum <= 1000
Pattern lesson

See the pattern, then code

Prefix sum on a root-to-node path
Recognition clue

You are counting downward paths with a fixed sum that can start anywhere. 'Number of subarray-like segments summing to K' on a tree is the tree analogue of subarray-sum-equals-K, which points to prefix sums plus a hash map.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Along one root-to-current path, a segment ending at the current node sums to targetSum exactly when some earlier prefix equals (current prefix - targetSum). Keep a frequency map of prefix sums seen on the current path and look up that complement.

New words, made simpleKnow these before the algorithm
Prefix sum
The running total of node values from the root down to the current node.
Complement
The earlier prefix value (curr - targetSum) that would make the segment between it and now sum to the target.
Backtracking the map
Removing the current prefix count after exploring a subtree so it does not leak into sibling paths.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Path-start brute force

Recomputes overlapping paths repeatedly; too slow on skewed trees.

For every node, run a second DFS treating it as a path start and count downward paths summing to target.

Time O(n^2)Space O(h)
Best choicePrefix sum + hash map

Each node is visited once and every qualifying path is counted in O(1); optimal.

Carry a running prefix sum and a map of prefix frequencies along the current path; add the complement's frequency at each node.

Time O(n)Space O(n)
The rule we keep true

Invariant

The prefix map always contains exactly the prefix sums of the nodes on the path from the root to the current node's parent (plus the base 0).

Why this is correct

Reasoning

A downward path from ancestor A (exclusive) to current node C sums to targetSum iff prefix(C) - prefix(A) = targetSum, i.e. prefix(A) = prefix(C) - targetSum. Since the map holds every ancestor prefix on the live path, its count of that value is exactly the number of valid A's ending at C. Backtracking guarantees only true ancestors remain in the map.

The algorithm in three movesSay these aloud before coding
1DFS down the tree, accumulating a running prefix sum

prefix = {0:1, 10:1, 15:1}

2Add prefix[current - targetSum] to the count

at node 3: curr=18, need 18-8=10 -> +1

3Record the current prefix sum in the map before recursing into children

at node 2->1: curr=8, need 0 -> +1

4After both children return, decrement the current prefix to undo it (backtrack)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
100
51
-32
33
24
115
1 · Readnode 10
2 · AskIs 10-8=2 in map?
3 · Update stateprefix={0:1,10:1}
4 · Resultcount += 0
Key takeaway

Prefix sums accumulate down each path; a hit occurs when curr - targetSum was already recorded.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Seed the map with 0:1

    The empty prefix lets paths that start at the root be counted (curr - targetSum == 0).

  2. 2
    Lines 7-9Extend the prefix and count hits

    Add the node value, then look up how many earlier prefixes equal curr - targetSum.

  3. 3
    Lines 10-12Record and recurse

    Register the current prefix so descendants can use it, then explore both children.

  4. 4
    Lines 13Undo the prefix

    Decrement on the way back up so sibling branches never see this path's prefix.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty tree returns 0
  • Negative values and negative targetSum (why we cannot prune by sign)
  • A single path summing to target counted once, not for each start
  • Nodes with value 0 that create multiple valid subpaths
!

Common beginner mistakes

  • Forgetting to seed prefix={0:1}, missing paths that start at the root
  • Not decrementing the prefix after recursion, letting counts leak between siblings
  • Trying to prune with early exit as if all values were positive
Check your understanding

Why must we decrement prefix[curr] after visiting the children instead of leaving it?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split