#437 Path Sum III
the problem
In plain words
Count the paths whose values add up to targetSum. Here a path may start at any node and end at any node below it, but it must go downwards only (parent to child). It doesn't have to start at the root or end at a leaf.
in root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
out 3
5 → 3, 5 → 2 → 1 and -3 → 11.
in root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
out 3
5 → 4 → 11 → 2, 5 → 8 → 4 → 5 and 4 → 11 → 7.
- 0 ≤ number of nodes ≤ 1000
- -10⁹ ≤ Node.val ≤ 10⁹
- -1000 ≤ targetSum ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternPrefix sum + HashMapTree DFS (top-down)
It's Subarray Sum Equals K on every root-to-node path. With prefix sums from the root, the path from just below ancestor A down to node X adds up to target exactly when prefix(X) − prefix(A) = target. A HashMap of the prefixes on the current path answers that in O(1) — just take each prefix back out when you leave its node.
solutions
From brute force to optimal
For each node, count the downward paths that start there; add those counts over all nodes.
- pathSum(root) = countFrom(root) + pathSum(left) + pathSum(right).
- countFrom(node, remaining): subtract node.val; count 1 if it hits 0; continue into both children.
Each node is walked once from every ancestor (and itself): O(n log n) when balanced, O(n²) for a chain.
Two recursions stacked, each at most h deep.
class Solution { public int pathSum(TreeNode root, int targetSum) { if (root == null) return 0; return countFrom(root, targetSum) // paths that start at this node + pathSum(root.left, targetSum) // ...or start somewhere lower + pathSum(root.right, targetSum); } /** Downward paths that start exactly at node and add up to `remaining` (long: sums overflow int). */ private int countFrom(TreeNode node, long remaining) { if (node == null) return 0; remaining -= node.val; return (remaining == 0 ? 1 : 0) + countFrom(node.left, remaining) + countFrom(node.right, remaining); }}Carry the prefix sum down. At each node, count how many prefixes above it equal sum − target; then add its own prefix for its descendants and remove it on the way back.
- seen = {0: 1} — the empty prefix, so paths that start at the root count.
- sum += node.val.
- count += seen.getOrDefault(sum − target, 0).
- seen.merge(sum, 1, Integer::sum); recurse left and right.
- seen.merge(sum, −1, Integer::sum) before returning.
One visit per node with O(1) average HashMap work.
The map can keep one key per node (counts drop to 0 instead of vanishing); only the current path's prefixes are non-zero. Plus O(h) recursion.
class Solution { public int pathSum(TreeNode root, int targetSum) { Map<Long, Integer> seen = new HashMap<>(); // prefix sums on the current root path → how many seen.put(0L, 1); // the empty prefix: lets a path start at the root return walk(root, 0L, targetSum, seen); } private int walk(TreeNode node, long sum, int target, Map<Long, Integer> seen) { if (node == null) return 0; sum += node.val; // prefix sum from the root to this node int count = seen.getOrDefault(sum - target, 0); // paths that END here seen.merge(sum, 1, Integer::sum); // now my descendants can see me count += walk(node.left, sum, target, seen) + walk(node.right, sum, target, seen); seen.merge(sum, -1, Integer::sum); // leaving: my siblings must not see me return count; }}Dry run
in the room
How to say it in the interview
talk track
- Start with the O(n·h) answer: for each node, count the paths that start there.
- Then connect it to Subarray Sum Equals K: every root-to-node path is an array, and prefix sums turn "a range adds up to k" into "two prefixes differ by k".
- Explain the two details: seed {0: 1} so paths from the root count, and undo each prefix when you leave its node so sibling branches never mix.
- Use long for the sums: values reach ±10⁹.
traps
- Forgetting the undo: a prefix from the left branch stays in the map and pairs up with a node in the right branch — a "path" that turns, which isn't allowed.
- Forgetting
seen.put(0L, 1): paths that start at the root are never counted. - int sums: 10⁹ + 10⁹ + … wraps around; one LeetCode test is built to catch exactly this. Use long.
- Storing the current prefix before the lookup: with target 0, every node would pair with itself and count an empty path.
what they ask next
Follow-ups
Why not a sliding window?
Values can be negative, so you can't tell when to shrink the window — the same reason Subarray Sum Equals K uses a HashMap.
Return the paths themselves?
Keep the current path's nodes on a stack next to their prefixes. For each match, the path runs from just below the ancestor whose prefix equals sum − target down to the current node.
before you submit
Edge cases to test
- Empty tree → 0.
- Zeros: [0,0,0] with target 0 → 5 (three single nodes and two pairs).
- Values near 10⁹ down a chain: int sums wrap around and invent paths — use long.
practise next
Similar problems
- #560Subarray Sum Equals KMediumin Hashing
- #112Path SumEasyin Tree Recursion
- #113Path Sum IIMediumin Tree Recursion