Path Sum: The Top-Down DFS Pattern for Root-to-Leaf Paths

Path Sum is where most people first meet the idea that a recursive call can carry information downward instead of only handing an answer back up. The question sounds trivial — does some root-to-leaf path add up to a target? — but the clean way to answer it flips how beginners usually think about tree recursion.

The trap is checking the sum in the wrong place. A path sum is only valid at a leaf, not at any internal node you happen to pass. Get the running total and the leaf test right, and the whole solution is about ten lines.

The top-down version threads a running sum through each recursive call, so every node already knows the sum of everything above it the moment it's entered. That framing generalizes to almost every other root-to-leaf question you'll see.

The problem#

Given the root of a binary tree and an integer target, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals target. A leaf is a node with no children.

Two constraints quietly shape the solution:

• The sum only counts at a leaf. 5 → 4 = 9 is not a valid path even if 9 were the target, because 4 still has a child.
• Values can be negative, so you cannot prune a branch just because the running sum already passed the target. You must reach the leaf to decide.

The brute force baseline#

The literal approach: enumerate every root-to-leaf path as an explicit list, sum each one, and check for a match.

This gives the right answer, but it's wasteful. Every path is materialized into its own array ([...path, node.val] copies the whole prefix at each node), and every path is summed after it's fully built. On a tree with n nodes and height h, storing paths costs up to O(n·h) extra memory, and you do the summation work twice — once implicitly by copying, once explicitly with reduce. You never needed the paths themselves. You only needed one boolean.

The key insight: carry the sum down, not up#

Instead of building paths and summing them afterward, accumulate the sum as you descend. When you enter a node, its running sum is just the parent's running sum plus its own value. Pass that number into each child call. By the time you land on a leaf, the running sum already equals the total of the entire path from the root — no separate summation pass, no stored paths.

This is the top-down DFS pattern: state flows down through the recursion as an argument, and each node acts on the accumulated context it inherited. Contrast it with bottom-up recursion, where a node computes something from its children's return values on the way back up. Here the work happens on the way in.

To report the result, keep a single boolean ans in the enclosing scope. Whenever a leaf's running sum matches the target, flip it to true. Once it's true, it stays true — the answer is locked in even as other branches keep exploring.

The optimal solution#

This mirrors the algorithm the Path Sum - Top Down visualizer steps through line by line.

Three details make it correct:

• traverse(root, 0) seeds the running sum at 0, so the root's newSum becomes exactly its own value.
• The leaf gate !curr.left && !curr.right is the only place a comparison happens. Internal nodes never test their sum against the target.
• ans = ans || true never un-sets a match. A later branch that fails cannot overwrite a true found earlier.

The curr.left && traverse(...) guards mean recursion only descends into children that exist — null children are simply skipped instead of triggering an empty call.

Walkthrough#

Trace the tree above with target = 20. Recursion explores left before right, and currSum is the value passed in to each call.

The order is the whole story. 5 adds itself (sum 5) and recurses left. 4 inherits 5, becomes 9, and recurses into its only child. 11 inherits 9, becomes 20, is a leaf, and matches — ans flips to true. Control unwinds back to 5, which now tries its right child 8: it inherits 5, becomes 13, is a leaf, and fails. That failure is harmless because ans is already true and ans || true can't reverse it.

Notice 11 never sees 8's value and 8 never sees 4's — each branch inherits only the sum along its own path from the root. That isolation is exactly what passing the sum by value gives you for free.

Complexity#

Height h is O(log n) for a balanced tree and O(n) for a fully skewed one (a linked-list-shaped tree), so worst-case space is O(n). The brute-force version is also O(n) time but adds up to O(n·h) space to store every path — pure overhead this solution avoids by keeping only a single integer and a single boolean.

Common mistakes#

• Checking the sum at internal nodes. The comparison belongs inside the leaf gate only. Testing newSum === target at every node reports paths that stop in the middle of the tree, which aren't valid root-to-leaf paths.
• Forgetting the empty-tree case. With no root, there is no path at all, so the answer is false. Skipping the if (!root) return false guard either crashes or, worse, returns true for target = 0.
• Pruning on negative values. You can't stop early because the running sum overshot the target — a later negative node can bring it back down. Every path must reach its leaf.
• Un-setting ans on a failing branch. Writing ans = (newSum === target) instead of ans = ans || true lets a later mismatched leaf overwrite an earlier success. Once a match is found, it must stick.
• Treating a single node as a non-leaf. A tree with just a root is a root-to-leaf path of length one. hasPathSum([7], 7) should return true.

Where this pattern shows up next#

Top-down DFS — pushing accumulated state down as a recursion argument and acting on it at the right node — is the backbone of most binary-tree traversals. These siblings drill the same descent-and-compare muscle:

• Same Tree — walk two trees in lockstep, comparing node values as you descend.
• Symmetric Tree — a mirror-image DFS that pairs left-of-one with right-of-the-other.
• Symmetric Tree - Iterative — the same mirror check driven by an explicit stack instead of recursion.
• Subtree of Another Tree — anchor a full-tree comparison at every node of a larger tree.

You can also step through Path Sum interactively to watch the running sum accumulate down each branch and the ans flag flip at the matching leaf.

FAQ#

Why check the sum only at leaves instead of at every node?#

Because the problem defines a path as running from the root all the way to a leaf. An internal node has more path below it, so its running sum is a partial total, not a complete path. Comparing at internal nodes would accept paths that stop early — for example counting 5 → 4 = 9 as a valid answer even though 4 still has a child. The !curr.left && !curr.right gate ensures only completed root-to-leaf paths are tested.

What is the difference between top-down and bottom-up path sum?#

Top-down carries the running sum down as a function argument, so each node already knows the accumulated total above it and simply checks it at the leaves. Bottom-up instead subtracts each node's value from the remaining target and returns a boolean up the call stack (return hasPathSum(left, target - val) || hasPathSum(right, target - val)). Both are O(n) time and O(h) space; they're the same computation viewed from opposite directions. Top-down tends to read more naturally when you want to reason about "the sum so far."

Does Path Sum work with negative node values?#

Yes, and negatives are exactly why you can't shortcut the traversal. With only positive values you might be tempted to abandon a branch once the running sum exceeds the target, but a negative value further down can pull the total back to the target. Because of that, the algorithm always descends to the leaf before deciding, which keeps it correct for any mix of positive, negative, and zero values.

What is the time and space complexity of the top-down solution?#

Time is O(n) because every node is entered exactly once and does constant work — one addition and, at leaves, one comparison. Space is O(h) for the recursion stack, where h is the tree height: O(log n) for a balanced tree and O(n) for a completely skewed one. It never stores the paths themselves, so it uses far less memory than a brute-force approach that materializes each root-to-leaf path.

How does the ans boolean avoid missing or losing a match?#

ans starts as false and is only ever updated with ans = ans || true, which can flip it to true but never back to false. That means the first matching leaf locks the answer in, and any branches explored afterward — including failing leaves — cannot overwrite it. When the traversal finishes, ans reflects whether any root-to-leaf path matched, which is precisely what the problem asks.