Path Sum: Root-to-Leaf DFS With a Shrinking Target
Solve Path Sum with a depth-first search that shrinks the target as it descends — intuition, JavaScript code, a worked walkthrough, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Path Sum is the problem where recursion on trees finally clicks. The prompt sounds like it needs bookkeeping — track every path, sum each one, compare against a target — but the elegant solution never builds a single path or holds a running total. It just asks one small question at every node and lets the call stack do the rest.
The trick is a reframe: instead of adding up as you go down, you subtract down. Each node hands its children a slightly smaller target, and the whole problem collapses to a single check at the leaves.
The problem
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path where the values along the path add up to targetSum. A leaf is a node with no children.
Input: root = [5,3,4,null,null,11], targetSum = 20
Output: true // the path 5 -> 4 -> 11 sums to 20Two words carry all the weight:
- Root-to-leaf. The path must start at the root and end at an actual leaf. A partial path that hits the target halfway down does not count.
- Leaf. You only compare against the target at a node with no children. Stopping early — or counting an internal node as an endpoint — is the single most common bug.
The brute force baseline
The literal reading of the problem: enumerate every root-to-leaf path, sum each one, and check for a match.
function hasPathSum(root, targetSum) {
const paths = [];
function collect(node, path) {
if (!node) return;
path.push(node.val);
if (!node.left && !node.right) {
paths.push([...path]); // full root-to-leaf path
} else {
collect(node.left, path);
collect(node.right, path);
}
path.pop();
}
collect(root, []);
return paths.some((p) => p.reduce((a, b) => a + b, 0) === targetSum);
}This works, but it does far too much. It materializes every path into an array, stores them all, then re-sums each from scratch. On a tree with L leaves and height h, you copy up to O(L · h) values and re-add them afterward. You are also computing full sums even for paths that could have been abandoned early. Nothing here needs to be remembered — and that is the opening.
The key insight: subtract the target on the way down
Flip the direction of the arithmetic. Rather than summing values upward at the end, spend the target as you descend.
At the root, you need a path summing to targetSum. After you "use" the root's value, the rest of the path (through either child) only needs to sum to targetSum - root.val. That smaller number is exactly the target you pass down. Recurse, and each level shaves off one more node's value.
By the time you reach a leaf, the question has shrunk to a single comparison: does this leaf's value equal the target that arrived here? If yes, the values along this path summed perfectly. This is depth-first search with a shrinking target, and it needs no path array and no running total.
The optimal solution
function hasPathSum(root, targetSum) {
if (root === null) {
return false;
}
if (!root.left && !root.right) {
return targetSum === root.val;
}
const remaining = targetSum - root.val;
return hasPathSum(root.left, remaining)
|| hasPathSum(root.right, remaining);
}Three cases, in the order that matters:
- Empty subtree (
root === null) returnsfalse. This handles both an entirely empty tree and, more importantly, the null child of a node that has only one real child — you must not treat a one-child node as a leaf. - Leaf (
!root.left && !root.right) returns whether the remaining target exactly equals the leaf's value. This is the only place a real answer is decided. - Internal node subtracts its value and asks the same question of each child. The
||short-circuits: if the left subtree already found a valid path, the right subtree is never explored.
The null-check ordering is deliberate. Because a missing child returns false before the leaf test runs, a node with exactly one child never gets mistaken for a leaf — its single real child is forced to carry the full remaining target.
Walkthrough
Trace root = [5,3,4,null,null,11], targetSum = 20. That tree is 5 at the root, with left leaf 3 and right child 4, whose left child is leaf 11.
| Call | targetSum in | node.val | Leaf? | Work | Returns |
|---|---|---|---|---|---|
hasPathSum(5, 20) | 20 | 5 | no | remaining = 20 − 5 = 15, recurse left | pending |
hasPathSum(3, 15) | 15 | 3 | yes | 15 === 3? no | false |
| back at node 5 | — | — | — | left was false, recurse right with 15 | pending |
hasPathSum(4, 15) | 15 | 4 | no | remaining = 15 − 4 = 11, recurse left | pending |
hasPathSum(11, 11) | 11 | 11 | yes | 11 === 11? yes | true |
| unwind | — | — | — | node 4 returns true, node 5 returns true | true |
The leaf 3 is the dead end: the target that reached it was 15, but the leaf holds 3, so that path fails and the search backtracks to node 5. The right branch spends 5 then 4, leaving exactly 11 for the leaf 11 — a perfect match. The moment a leaf returns true, the || chain carries it straight back up without touching any remaining branches.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(n) | each of the n nodes is visited at most once; constant work per node |
| Space | O(h) | recursion stack depth equals the tree height h |
Time is linear because a single DFS touches every node at most once and does only a subtraction and a comparison at each. Space is the call-stack depth: O(log n) for a balanced tree, degrading to O(n) for a fully skewed (linked-list-shaped) tree. The brute-force version, by contrast, also spends extra space storing every full path.
Common mistakes
- Treating a one-child node as a leaf.
!node.left && !node.rightis the only correct leaf test. Checkingnode.left === null || node.right === nullwould wrongly stop at internal nodes that happen to have one missing child. - Comparing the target at internal nodes. The equality check belongs at leaves only. An internal node whose value happens to equal the remaining target is not a valid endpoint.
- Passing
0instead offalsefor null subtrees. An empty subtree has no path; returningfalse(not "sum reached 0") keeps single-child nodes honest. - Forgetting negative values. Node values can be negative, so the running total is not monotonic — you cannot prune a branch just because the remaining target went negative. Only the leaf comparison is authoritative.
- Re-summing whole paths. If you find yourself building a list of visited values and adding them at the leaf, you have rebuilt the brute force. The subtraction carries the sum for free.
Where this pattern shows up next
The "shrink the target as you recurse, decide at the leaf" shape is a launchpad for the rest of the tree-DFS family:
- Path Sum - Top Down — the same problem carrying a running sum downward instead of a shrinking target, a useful contrast for building intuition.
- Binary Tree Maximum Path Sum — where paths can bend through a node, and each call returns a value up to its parent.
- Symmetric Tree — a mirror-comparison DFS that pairs two subtrees instead of one target.
- Symmetric Tree - Iterative — the same mirror check reworked with an explicit stack, the manual version of the recursion here.
You can also step through Path Sum interactively to watch the target shrink node by node and the call stack unwind on a match.
FAQ
Why subtract the target instead of adding a running sum?
Subtracting keeps each recursive call self-contained: every node only needs the remaining target, not the history of what came before. When you reach a leaf, one comparison (remaining === node.val) settles the whole path. Adding a running sum works too, but then you must also pass the original target down so the leaf can compare against it — two pieces of state instead of one. Both are O(n); subtraction is just leaner.
What is the time and space complexity of Path Sum?
Time is O(n), where n is the number of nodes, because a single depth-first search visits each node at most once and does constant work per node. Space is O(h), where h is the tree height, from the recursion call stack — O(log n) for a balanced tree and O(n) for a skewed one. The || short-circuit can end the search early on a match but does not change the worst-case bounds.
How do I detect a leaf correctly?
A leaf is a node with both children missing: !node.left && !node.right. Test both at once. If you stop at any node with a single missing child, you will treat internal nodes as endpoints and get wrong answers. In this solution, the separate root === null guard runs first, so a node's one real child is always forced to carry the target rather than being skipped.
Does Path Sum work with negative node values?
Yes, and it needs no changes. Because the algorithm only decides at leaves, negative values are handled automatically — the remaining target can go up or down as you descend, and a negative node simply increases the target for its children. The one thing you must not do is prune a branch early when the remaining target turns negative, since a later negative node could bring it back to zero.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.