Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Walk root-to-leaf paths with DFS, subtracting each node's value from the target as you descend. At a leaf, return whether the remaining target equals exactly that leaf's value (equivalently, whether the running remainder hit zero). The trick is the leaf test: a node with no children is the only place you may declare success — never an internal node, never a null child.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you correctly identify the leaf as the only valid place to succeed, handle null children as false, and propagate the shrinking remainder down the tree instead of trying to compare a total at the end.
Where candidates slip
Returning true at a node whose value alone equals the remaining target even though it still has children, or treating a null child as a valid zero-sum path — both falsely report success.
How to stand out
State the leaf invariant explicitly ('I only check the sum where both children are null'), note that negative values forbid pruning, and offer the iterative stack variant carrying (node, remaining) pairs.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAt a node: subtract node.val from targetIs node null?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Recursive DFS with a Shrinking Remainder
1Hint 1Explore hintHide hint
You're looking for a path from root to a leaf. As you step into a child, how does the amount you still need to collect change?
2Hint 2Explore hintHide hint
Subtract the current node's value from the target before recursing. Then the question at each node becomes 'can the rest of the path make up the new remainder?'
3Hint 3Explore hintHide hint
The base of the recursion is the leaf: a node with no children succeeds only if the remaining target now equals that node's value (i.e., the remainder after subtracting hit zero). A null node is always false.
A · Core idea
The reframe that makes this trivial is to push state down the recursion. Instead of carrying an accumulating sum upward and comparing it at the end, we carry the remaining target downward. Each time we descend into a node we subtract that node's value from the target. The recursive question is then uniform at every node: 'starting here with this much left to collect, does a leaf-terminated path reach exactly zero?'
Why the decision belongs at the leaf and nowhere else. The problem defines a valid path as root-to-leaf. So the only moment we are allowed to declare victory is when we stand on a node with no children — that is the end of a complete path. If we instead returned true the moment remainder == node.val at an internal node, we'd be accepting a path that stops in the middle of the tree, which the problem forbids. The leaf guard node.left == null && node.right == null is therefore not a performance tweak, it is the definition of correctness here.
Why a null node must return false, not true. It is tempting to write the base case as if (node == null) return target == 0. That is subtly wrong: consider a node with exactly one child and a remainder that happens to be zero. The missing child is a null, and if null returned true on a zero remainder, we'd falsely accept a path that never actually reached a leaf. Treating null as an unconditional false and putting the success test at the genuine leaf avoids this entire class of bug. The single-child case then correctly recurses only into the real child.
Why we OR the two recursive calls. We need some path to work, not all of them. So the result at an internal node is leftSucceeds || rightSucceeds. Short-circuit evaluation is a nice bonus — the instant the left subtree reports success, we never touch the right subtree. But the logical core is simply existential: one good path anywhere below is enough.
Why negative values block pruning. With all-positive values you could stop descending once the remainder dropped below the smallest possible future contribution. Here values range down to -1000, so a remainder of -7 today might be repaired by a -(-) ... actually by adding a negative node that pushes it back. Concretely, a later node of value -5 changes the remainder by subtracting -5, i.e. adding 5. Because the remainder can move in either direction, no early-exit pruning on its sign is safe — you must walk every root-to-leaf path until it ends.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [5,4,8,11,null,13,4,7,2], targetSum = 22Interactive diagram
The winning path 5 → 4 → 11 → 2
node 5, rem 22The highlighted spine sums to 22 and ends at a leaf; the remainder reaches 0 exactly at node 2.
trueC · Code with teaching comments
Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
The state you propagate is the remaining target, not the accumulated sum. That single design choice — push the shrinking remainder down rather than bubble a total up — is what makes the leaf test a clean remainder == 0 and generalizes directly to Path Sum II (carry the partial path too) and beyond.
ComplexityO(n) time, O(h) space — Each node is visited at most once, so time is O(n). The recursion depth is the tree height h, giving O(h) stack space — O(log n) for a balanced tree, O(n) for a degenerate (linked-list-shaped) tree.
E · Edge cases and pitfalls7root = [], targetSum = 0 — Root is null → return false immediately. An empty tree has no root-to-leaf path.Explore edge casesHide edge cases
Edge cases handled
root = [], targetSum = 0Root is null → return false immediately. An empty tree has no root-to-leaf path.root = [1,2], targetSum = 1Node 1 leaves remainder 0 but it is NOT a leaf (has child 2); recurse into 2 → remainder -1 at leaf → false. Demonstrates the leaf guard.root = [-2,null,-3], targetSum = -5Negative values: -2 then -3 (a leaf) gives remainder 0 → true. Confirms pruning on sign would be wrong.
Pitfalls
- Writing the base case as `if (node == null) return target == 0` — falsely accepts a missing child as a valid path on a single-child node.
- Returning true at an internal node when remainder == node.val, ignoring that the path must reach a leaf.
- Pruning when the remainder goes negative — invalid because later nodes can be negative.
- Forgetting the empty-tree case and dereferencing a null root.
Approach 2 of 2 · Optimal
Iterative DFS with an Explicit Stack
1Hint 1Explore hintHide hint
Recursion remembers, per call, which node you're at and how much target is left. To remove recursion, store those two facts yourself on a stack.
2Hint 2Explore hintHide hint
Push pairs of (node, remaining-after-this-node). Pop one, and if it's a leaf with remaining == 0, you've found a path.
3Hint 3Explore hintHide hint
For each non-leaf popped, push its non-null children with the remaining target reduced by the child's value.
A · Core idea
This is the same algorithm with the call stack made explicit, useful when the interviewer says 'no recursion' or when the tree could be deep enough to risk a stack overflow. The unit of state we save is a pair: a node and the target remaining after that node's value has been accounted for.
Why store the remaining target alongside the node. In the recursive version the remaining target lived in each stack frame as a parameter. Removing recursion means we must carry that same number ourselves. So each stack entry is (node, remaining) where remaining already has node.val subtracted out — the node arrives pre-credited, so the leaf test is again a clean remaining == 0.
Why the leaf test is unchanged. Correctness still depends on declaring success only at a genuine leaf. When we pop (node, remaining), we check node.left == null && node.right == null && remaining == 0. If that holds, return true immediately. Otherwise we push whichever children exist, each with remaining - child.val. Null children are simply never pushed, which is the iterative analog of the recursive null-returns-false rule.
Why a stack and not a queue. Either works for an existence query, because we're not after the shortest or first path in any particular order — we just need some path. A stack gives depth-first behavior (dive down one path fully before backtracking), which tends to find a deep matching path with a smaller frontier; a queue would explore breadth-first. The choice doesn't affect correctness, only traversal order and peak memory shape.
Why this matches recursion on complexity. We touch each node once and the live frontier on the stack never exceeds the current path length, so time is O(n) and space is O(h) — identical to recursion, just with the bookkeeping moved off the language runtime and into our own container.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,2,3], targetSum = 5Interactive diagram
Where you're allowed to declare success
push rootThe whole problem hinges on checking the sum only at leaves — the green nodes — never at internal nodes.
falseC · Code with teaching comments
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
The state you'd normally pass as a recursion parameter (the remaining target) becomes part of the stack entry. Recognizing 'a recursion parameter must become a tuple on my explicit stack' is the general recipe for converting any DFS to iterative form.
ComplexityO(n) time, O(h) space — Every node is pushed and popped exactly once → O(n) time. The stack holds at most one root-to-leaf path's worth of nodes along the current DFS frontier, bounded by the height h → O(h) space.
E · Edge cases and pitfalls7root = [1], targetSum = 1 — Push (1,0); pop it, it's a leaf with rem 0 → return true.Explore edge casesHide edge cases
Edge cases handled
root = [1], targetSum = 1Push (1,0); pop it, it's a leaf with rem 0 → return true.root = [1,2], targetSum = 1Push (1,0); pop — node 1 is NOT a leaf (has child 2), so no match; push (2,-1); leaf with rem -1 → false.Deep skewed tree of 5000 nodesExplicit stack avoids recursion depth limits; O(h) frontier handles it where recursion might overflow.
Pitfalls
- Checking rem == 0 without also confirming the node is a leaf — accepts mid-path stops.
- Pushing null children onto the stack, then dereferencing them later.
- Forgetting to subtract the child's value when pushing, so the remainder never shrinks correctly.
- Mismatching the two parallel stacks (node vs remaining) by pushing to one but not the other.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; Deque<TreeNode> nodes = new ArrayDeque<>(); Deque<Integer> remaining = new ArrayDeque<>(); nodes.push(root);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Treating a null child as a valid zero-sum path
Putting the success test on the null base case means a single-child node whose remainder is zero falsely succeeds through its missing child, even though no leaf was reached.
Explore the code comparisonHide the code comparison
Treating a null child as a valid zero-sum path
Putting the success test on the null base case means a single-child node whose remainder is zero falsely succeeds through its missing child, even though no leaf was reached.
Don't write this
if (root == null) return targetSum == 0; // wrong: null is not a leaf
return hasPathSum(root.left, targetSum - root.val)
|| hasPathSum(root.right, targetSum - root.val);Write this instead
if (root == null) return false;
int remaining = targetSum - root.val;
if (root.left == null && root.right == null) return remaining == 0;
return hasPathSum(root.left, remaining)
|| hasPathSum(root.right, remaining);2Succeeding at an internal node
The path must end at a leaf. Returning true the moment the remainder equals the node value ignores that the node still has children, accepting an illegal mid-tree stop.
Explore the code comparisonHide the code comparison
Succeeding at an internal node
The path must end at a leaf. Returning true the moment the remainder equals the node value ignores that the node still has children, accepting an illegal mid-tree stop.
Don't write this
def hasPathSum(self, root, targetSum):
if root is None:
return False
if targetSum == root.val: # wrong: ignores children
return True
return (self.hasPathSum(root.left, targetSum - root.val)
or self.hasPathSum(root.right, targetSum - root.val))Write this instead
def hasPathSum(self, root, targetSum):
if root is None:
return False
remaining = targetSum - root.val
if root.left is None and root.right is None:
return remaining == 0
return (self.hasPathSum(root.left, remaining)
or self.hasPathSum(root.right, remaining))3Pruning on a negative remainder
With positive-only values you could stop when the remainder went negative, but here values reach -1000, so a negative remainder can still be corrected by a later negative node.
Explore the code comparisonHide the code comparison
Pruning on a negative remainder
With positive-only values you could stop when the remainder went negative, but here values reach -1000, so a negative remainder can still be corrected by a later negative node.
Don't write this
int remaining = targetSum - root.val;
if (remaining < 0) return false; // unsafe with negative node values
if (root.left == null && root.right == null) return remaining == 0;Write this instead
int remaining = targetSum - root.val;
if (root.left == null && root.right == null) return remaining == 0;
return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);Revise
Carry the pattern into the interview
Pattern to remember
Root-to-leaf DFS with a shrinking remainder
Code pattern to memorize
hasPathSum(node, target):
if node is null: return false
target -= node.val
if node.left is null and node.right is null:
return target == 0 # leaf: did we land exactly?
return hasPathSum(node.left, target)
or hasPathSum(node.right, target)Rules to remember
- 1Success is only declared at a leaf (both children null) — never at an internal node and never on a null child.
- 2Subtract
node.valfrom the target on the way down, then checkremainder == 0at the leaf — don't accumulate and compare at the end unless you carry the sum explicitly. - 3A
nullnode returns false, not true — an empty child is not a zero-length valid path. - 4Values can be negative, so you cannot prune a branch just because the remainder went negative.
- 5Use OR across the two children — one valid path anywhere is enough to return true.
Use this pattern when
- Asked whether ANY root-to-leaf path hits an exact target sum
- You only need a yes/no answer, not the path itself
- The path must start at the root and end at a leaf (not any node-to-node path)
- Tree may contain negative values, ruling out greedy pruning
Choose another pattern when
- Need the actual list of paths → Path Sum II, collect the path then backtrack
- Path may start/end anywhere, not root-to-leaf → Path Sum III or Max Path Sum (prefix sums / post-order)
- Counting paths instead of existence → Path Sum III with a prefix-sum hash map
- All values guaranteed positive AND you want to prune → still works, but the leaf check is what matters
Interview takeaway
Path Sum is the cleanest template for root-to-leaf DFS: push state (the remaining target) down the recursion and make the decision only at the leaf. Internalize the leaf guard and the null-returns-false rule, and the whole Path Sum family becomes variations on this single skeleton.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternRoot-to-leaf DFS carrying state downward. Recognise it whenever a property is defined over complete paths from the root to a leaf. The skeleton — null returns the failure value, decide at the leaf, OR/aggregate over children — underlies Sum Root to Leaf Numbers, Path Sum II, and Binary Tree Paths.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Path Sum IIComing soonReturn every root-to-leaf path that sums to target — carry the partial path and backtrack on the way up.
- Path Sum IIIComing soonCount paths that may start and end anywhere — prefix-sum hash map of running sums.
- Binary Tree Maximum Path SumAny node-to-node path; post-order returning the best downward arm at each node.
- Sum Root to Leaf NumbersSame root-to-leaf DFS, but build a number digit-by-digit instead of testing a sum.