Path Sum
Problem Statement
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all node values along the path equals targetSum. A leaf is a node with no left child and no right child.
Input
The root pointer of a binary tree and an integer targetSum.
Output
A boolean: true if at least one root-to-leaf path sums to targetSum, otherwise false.
Constraints
- •
0 <= number of nodes <= 5000 - •
-1000 <= Node.val <= 1000 - •
-1000 <= targetSum <= 1000
Examples
Example 1
root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
trueExample 2
root = [1,2,3], targetSum = 5
falseExample 3
root = [], targetSum = 0
falseLearning Objectives
- Recognise root-to-leaf path questions as top-down recursion with carried state.
- Track the remaining target by subtracting the current node value at each step.
- Check the target only at a true leaf, where both children are **null**.
- Use short-circuiting to stop once any valid path is found.
Intuition
Pattern Recognition
The signal is a question about a root-to-leaf path and a target that changes as you move downward. Unlike diameter, there is no need to combine two children into one answer. The natural state flows top-down: after choosing a node, subtract its value from the remaining sum and ask a child to finish the job.
The trap is the leaf definition. A path is valid only if it ends at a node with both children null. You cannot return true just because the remaining sum becomes 0 at an internal node, and you cannot treat a missing child as a completed path.
Common mistakes
- ×Checking **remaining == 0** before confirming the current node is a leaf.
- ×Treating a **null** child as a successful endpoint when the remaining sum is **0**.
- ×Subtracting the node value after the recursive calls instead of passing the reduced target downward.
- ×Forgetting that negative values are allowed, so overshooting the target is not a valid pruning rule.
Algorithm Explanation
Key idea
Carry one value downward: the remaining sum needed from the current node to some leaf. At each node, subtract node.val. If the node is a leaf, return whether the new remaining sum is 0. If it is not a leaf, recursively ask the left or right child to complete the path.
Recursion walkthrough
For [5,4,8,11,null,13,4,7,2,null,null,null,1] with target 22, start at 5 and reduce the remaining sum to 17. Move to 4, reduce to 13. Move to 11, reduce to 2. The leaf 7 would reduce the remaining sum to -5, so that branch fails.
The sibling leaf 2 reduces the remaining sum from 2 to 0. Because 2 has no left child and no right child, this is a complete root-to-leaf path, so the recursion returns true. That success bubbles back through 11, 4, and 5 without needing to explore every other branch.
Algorithm
- If root is null, return false because there is no path.
- Subtract root.val from targetSum to get the remaining sum after using this node.
- If root is a leaf, return whether the remaining sum is 0.
- Recursively check the left child with the remaining sum.
- Recursively check the right child with the remaining sum.
- Return true if either child can complete a valid path.
Solutions
Solution: Top-down remaining target DFS
Use this direct recursive solution when the problem asks whether any root-to-leaf path satisfies a target.
Pass the remaining target downward. Each node consumes its own value. Only a leaf is allowed to decide success, because the path must end exactly at a leaf.
Step-by-step
- Return false immediately for an empty tree.
- Compute remaining = targetSum - root.val.
- If the current node is a leaf, return whether remaining == 0.
- Recursively search the left subtree using remaining.
- Recursively search the right subtree using remaining.
- Return the logical OR of the two child results.
O(n)
O(h)
In the worst case every node is visited once; recursion stack depth is the tree height.
Java implementation
Dry Run
Sample input
root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22. Follow the successful left-side branch and the failed sibling leaf.
| node | remaining before | remaining after subtract | leaf? | result returned |
|---|---|---|---|---|
| 5 | 22 | 17 | no | wait for a child |
| 4 | 17 | 13 | no | wait for a child |
| 11 | 13 | 2 | no | wait for a child |
| 7 | 2 | -5 | yes | false |
| 2 | 2 | 0 | yes | true |
| 11 | 13 | 2 | no | true because leaf 2 succeeds |
| 5 | 22 | 17 | no | true bubbles to the root |
The target check happens at leaf 2, not at internal nodes. Once that leaf returns true, the OR chain short-circuits upward.
Interview Tips
Lead with the invariant: the recursive parameter is the remaining sum needed from the current node down to a leaf. Then state the leaf test precisely as node.left == null && node.right == null. This problem is often used to catch candidates who accidentally accept partial paths that end before a leaf.
Likely follow-ups
- How would you return all root-to-leaf paths that sum to the target?
- How would you count paths with a target sum if they can start and end anywhere?
- How would you solve it iteratively with a stack of nodes and remaining sums?
- What changes if node values can be very large and sums may overflow an integer?
Similar Problems
Key Takeaways
- Root-to-leaf target problems often carry a remaining value downward.
- Subtract the current node value before recursing into children.
- A valid path must end at a true leaf, where both children are **null**.
- Short-circuit OR is safe because the question asks whether any valid path exists.