Path Sum
MediumSubtract as you descend, check at the leaf
Problem
Return whether the tree has a root-to-leaf path whose values sum to a target.
Subtract each node from the target as you descend; a leaf that hits exactly zero means success.
The idea
Carry the remaining target down, subtracting each node's value, and at a leaf ask whether the remainder is exactly zero. Subtracting on the way down avoids passing the accumulated path around.
The trick
- Only leaves count — a node with one child is not a leaf.
- Short-circuit with OR across the two children.
- Negative values mean you cannot prune on the remainder going negative.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [5,4,8,11], target=22 Values: 5, 4, 8, 11.
1dfs(node, rem):2 if leaf: return rem-node.val==03 rem-=node.val4 return dfs(left,rem) or dfs(right,rem)Input
- array
- [5, 4, 8, 11]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [5,4,8,11,null,13,4,7,2], target = 22
- Output:
- true
- Explanation:
- 5→4→11→2 adds to 22.
Example 2
- Input:
- tree = [1,2,3], target = 5
- Output:
- false
- Explanation:
- No root-to-leaf path makes 5 → false.
Example 3
- Input:
- tree = [1,2], target = 3
- Output:
- true
- Explanation:
- 1 + 2 = 3.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.