Path Sum
Does a root-to-leaf path exist whose values sum to targetSum?
- The number of nodes in the tree is in the range [0, 5000].
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
Intuition
The path sum problem asks whether any root-to-leaf path adds up to a target. The natural approach is to carry the remaining amount down the tree: at each node, subtract its value and ask the children to cover what is left. By the time you reach a leaf, the question has narrowed to a single comparison. That framing avoids accumulating a total and comparing at the bottom — instead the target shrinks as you descend, and at a leaf the test is simply whether the leaf's value equals what remains. The detail that decides correctness is where a path is allowed to end: - The path must terminate at a leaf — a node with no children — not at a null pointer. Getting this wrong is the standard bug. If you test the remaining target when you hit null, a node with exactly one child looks like a valid endpoint through its missing side, and the function reports paths that do not exist. Consider a root of 1 with a single left child of 2 and a target of 1: testing at null would find a "path" ending at the root, even though the root is not a leaf. So the leaf test must come before recursing, and a null child must contribute nothing rather than being treated as an ending. Note also that values may be negative, so you cannot prune a branch just because the remaining target has dropped below zero.
Root-to-leaf questions are top-down recursion: carry a running value into the call rather than returning one up. Subtracting as you descend means the leaf test is a single comparison against zero-remaining. The tell for this family is any phrase like "a path from the root to a leaf" — the answer is decided at leaves, so the leaf definition is the part to get exactly right.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Subtract as you descend
Define hasPath(node, remaining). On entering a node, the amount still to be covered by this subtree is remaining - node.val. Passing that down means no running total needs to be accumulated and compared later.
Handle the null node first
If the node is null, return false. This case is reached only from a parent that had a missing child, and a missing child is not a valid path ending — returning false here is what stops one-child nodes from being mistaken for leaves.
Test for a leaf before recursing
If the node has neither child, it is a genuine endpoint: return whether remaining == node.val. Placing this check before the recursive calls is what enforces the root-to-leaf requirement, and it is the single most important line in the solution.
Recurse into both children with an OR
Return hasPath(left, remaining - node.val) or hasPath(right, remaining - node.val). Either subtree may complete the path, and or short-circuits, so a match in the left subtree ends the search without touching the right.
Do not prune on negative remainders
It is tempting to abandon a branch once the remaining target goes negative, but node values can be negative, so a later node could bring the sum back up. That pruning is only valid when the problem guarantees non-negative values.
Cost of the traversal
In the worst case every node is visited once for O(n) time, though short-circuiting often ends the search much earlier. Space is O(h) for the recursion stack — O(log n) on a balanced tree, O(n) on a degenerate chain.
Solution & live demo
Common pitfalls
Treating any node with a null child as a leaf
if not root.left or not root.right:
return targetSum == root.valif not root.left and not root.right:
return targetSum == root.valA node with one child is not a leaf — the path must keep going. With or, a half-empty node ends the path early and reports a sum for a path that never reached a leaf. A leaf has both children missing.
Returning true when the running sum hits zero mid-path
if targetSum == 0: return True
if not root.left and not root.right:
return targetSum == root.valThe target must be met exactly at a leaf, not anywhere along the way. Values can be negative, so a path can hit the target mid-way and then move off it — stopping early answers a different question.
Returning true for an empty tree
if not root: return targetSum == 0
if not root: return False
A null node isn't a leaf and represents no path at all. Returning true there makes any node with one missing child succeed through its empty side, regardless of the values.
Edge cases
No root-to-leaf path exists → False even for target 0.
No pruning on sign — the target can recover; explore fully.