Path Sum III
Asked at TikTok
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Brute force: start a DFS from every node and count paths going down from it. That is O(n²) on a skewed tree.
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.
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.
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.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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)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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.