Skip to main content

437. Path Sum III

medium

Count downward paths whose node values sum to a target — paths don't need to start at root or end at a leaf. The naive O(n^2) walk works but a prefix-sum hash map cuts it to O(n).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Constraints

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

Examples

Example 1

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

Example 2

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

Example 3

Input
root = [], targetSum = 1
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force: from every node, run a DFS that counts paths starting there — O(n^2).

Hint 2

Optimal: track the running prefix sum from root and a hash map of prefix-sum frequencies seen along the current path.

Hint 3

At each node, the number of valid paths ending here equals the number of times (currentSum - targetSum) has appeared earlier on this root-to-node chain.

Solution approach

Reveal approach

Prefix-sum hash map. Maintain a counts dict mapping prefix-sum value -> how many ancestors on the current chain produced that sum; seed it with {0: 1} for the empty prefix. DFS from root: at each node, add node.val to the running sum; the number of paths ending at this node equals counts.get(currentSum - targetSum, 0). Add currentSum to counts, recurse into both children, then decrement currentSum's count before returning (backtrack) so siblings see only their own ancestor chain. O(n) time, O(h) space for recursion plus hash entries.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • dfs
  • prefix-sum
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta

Practice these live with InterviewChamp.AI

Drill Path Sum III and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →