MediumTreeDepth-First SearchBinary TreeUpdated Sep 2026

437. Path Sum III

Asked at TikTok

Difficulty

Medium

Time

O(n)

Space

O(h)

Pattern

Tree

Companies

1

Problem

You are given the root of a binary tree and an integer targetSum. Count how many paths in the tree have values that add up to exactly targetSum.

A path is a chain of nodes where each step goes from a parent to one of its children. The path does not have to start at the root and does not have to end at a leaf. It only has to go downwards — never back up, never sideways.

Return the number of such paths. Different paths are counted separately even if they share nodes. A single node counts as a path of length one.

Which downward chains sum to 8?

33-255+3 = 825+2+1 = 8110-3-3+11 = 811Three chains hit the target: 5→3, 5→2→1, and -3→11.
Paths may start anywhere and end anywhere, as long as every step goes from parent to child.

Constraints

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

Examples

Example 1
Inputroot = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output3
WhyThree downward chains add up to 8: 5 → 3, 5 → 2 → 1, and -3 → 11. Notice the first two start below the root, and the third starts on the right side.
Example 2
Inputroot = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output3
WhyThree chains sum to 22: 5 → 4 → 11 → 2, 5 → 8 → 4 → 5, and 4 → 11 → 7. Each one is a straight parent-to-child descent.

Asked At

1 companies
CompanyDifficulty
TikTokMediumView all TikTok questions →

How to Think About It

1

Brute force: start a DFS from every node and count paths going down from it. That is O(n²) on a skewed tree.

2

Key insight: along any root-to-node path, a downward sub-path ending at the current node sums to target exactly when currentPrefix - earlierPrefix == target. So count how many earlier prefixes equal currentPrefix - target.

3

Keep a hash map of prefix-sum counts for the nodes on the current path. Seed it with {0: 1} so paths starting at the root are counted.

4

Backtracking is essential: after exploring a node's children, decrement its prefix count. Otherwise prefixes from one branch leak into a sibling branch, where they are not ancestors.

5

Walkthrough: path 10 -> 5 -> 3 with target 8. Prefixes: 0, 10, 15, 18. At 18, look up 18 - 8 = 10 -> found once (the path 5 -> 3).

Optimal Approach

Step 1: count = {0: 1}.
Step 2: dfs(node, prefix):
If node is null, return 0.
prefix += node.val
res = count.get(prefix - target, 0)
count[prefix] += 1
res += dfs(node.left, prefix) + dfs(node.right, prefix)
count[prefix] -= 1 (backtrack)
Return res.
Step 3: Return dfs(root, 0).

Time: O(n). Space: O(h) for the recursion and the map.

Prefix sums along the current path

path 10 → 5 → 3sum = 81053Prefixes are 10, 15, 18. At 18 we ask: was 18 − 8 = 10seen before? Yes, so 5→3 is one path.count mapprefixseen01101151181The map stores how many times each prefix sum appearedon the current root-to-node path.prefix += node.valres = count[prefix − target]count[prefix] += 1 (go down)count[prefix] −= 1 (backtrack)
Keep a running sum from the root. A sub-path ending here sums to target when an earlier prefix equals current − target.
ComplexityTime O(n)Space O(h)Each node is visited once and does one hash-map lookup. h is the tree height, used by the recursion stack and the prefix map.

What Trips People Up in Real Interviews

1

Forgetting the backtrack step. The map must only contain prefixes of ancestors of the current node.

2

Leaving out the {0: 1} seed, which misses every path that starts at the root.

3

Stopping a path once it hits the target. Values can be negative, so a longer path might hit the target again.

4

Overflow in Java/C++: node values up to 10^9 along a deep path overflow 32-bit ints — use long for prefix sums.

Solution Code

O(n) time
def pathSum(root, targetSum):
    count = {0: 1}

    def dfs(node, prefix):
        if not node:
            return 0
        prefix += node.val
        res = count.get(prefix - targetSum, 0)
        count[prefix] = count.get(prefix, 0) + 1
        res += dfs(node.left, prefix) + dfs(node.right, prefix)
        count[prefix] -= 1
        return res

    return dfs(root, 0)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Path Sum III problem?

Path Sum III asks how many downward paths in a binary tree add up to a target, where a path can start and end at any node as long as it goes from parent to child. It is Subarray Sum Equals K moved onto a tree: prefix sums along the root-to-node path plus a hash map.

How do you solve Path Sum III?

The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Path Sum III?

Path Sum III is asked at TikTok. It is a medium difficulty problem.

What are common mistakes on Path Sum III?
  • Forgetting the backtrack step. The map must only contain prefixes of ancestors of the current node.
  • Leaving out the `{0: 1}` seed, which misses every path that starts at the root.
  • Stopping a path once it hits the target. Values can be negative, so a longer path might hit the target again.
  • Overflow in Java/C++: node values up to `10^9` along a deep path overflow 32-bit ints — use `long` for prefix sums.