02
Intuition
Carry the remaining target down: each node subtracts its value and asks its children to cover the rest. At a leaf, the answer is exact: does the leaf's value equal what's left?
03
Approach
1
Subtract as you descend
hasPath(node, t) → at a leaf, check t == node.val; otherwise recurse with t − node.val.
2
Leaf check is strict
The path must END at a leaf — a null child alone doesn't qualify, which is why the leaf test comes before recursing.
3
OR over children
Either subtree may complete the path; short-circuit on the first success.
04
Solution & live demo
python
▶1class Solution:
▶2 def hasPathSum(self, root, targetSum):
▶3 if not root: return False
▶4 if not root.left and not root.right:
▶5 return targetSum == root.val
▶6 rest = targetSum - root.val
▶7 return (self.hasPathSum(root.left, rest)
▶8 or self.hasPathSum(root.right, rest))
05
Edge cases
Empty tree
No root-to-leaf path exists → False even for target 0.
Negative values
No pruning on sign — the target can recover; explore fully.
06
Complexity
Time
O(n)
Space
O(h)
DFS, short-circuits on success.