Example 1
ready- Input
root = [ 5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1 ] targetSum = 22- Expected
true- Why
- the route 5 → 4 → 11 → 2 ends at a leaf and totals 22
Path Sum
25 min · hasPathSum()A route can hit the right total halfway down a tree and still be the wrong route. The finish line matters.
Given a binary tree's root and an integer targetSum, return true when at least one
root-to-leaf path — a downward route that starts at the root and ends at a node with
no children — has values adding to exactly targetSum.
Keep the endpoint rule sharp:
- A leaf has neither a left child nor a right child.
- Stopping at an internal node doesn't count, even if the running sum matches.
- Values and the target may be negative, zero, or positive.
- An empty tree has no root-to-leaf path, so it always returns
false.
Constraints
0 <= number of nodes <= 10_000-1_000 <= node.val <= 1_000-100_000_000 <= targetSum <= 100_000_000
Hints
Write down every finish
The direct approach collects the sum of each complete root-to-leaf route, then asks
whether targetSum appears in that collection.
Carry what remains
Instead of rebuilding a path at every leaf, subtract each visited value from the target. What must the remainder be when you reach a leaf?
Check the leaf, not just the number
A remainder of zero is an answer only when the current node has no children. Otherwise the route hasn't finished.
Follow-up
How would you return one matching root-to-leaf path instead of only true or false?
Visible cases
Examples
Example 2
ready- Input
root = [ 1, 2, 3 ] targetSum = 5- Expected
false- Why
- the complete route totals are 3 and 4, not 5
Example 3
ready- Input
root = [] targetSum = 0- Expected
false- Why
- an empty tree has no root-to-leaf route
Interview signal
Asked at
AmazonMetaBloomberg
Enumerate complete paths — total every finished route
Keep the values on the current route. At each leaf, sum that route and save the result. After every leaf has reported, check whether the target appears among the totals.
def has_path_sum(root: TreeNode | None, target_sum: int) -> bool:
if root is None:
return False
path: list[int] = []
path_sums: list[int] = []
def collect(node: TreeNode) -> None:
path.append(node.val)
if node.left is None and node.right is None:
path_sums.append(sum(path))
else:
if node.left is not None:
collect(node.left)
if node.right is not None:
collect(node.right)
path.pop()
collect(root)
return target_sum in path_sumsThis works, but sum(path) repeats work already done for the parent route.
Time O(nh) in the worst case — leaf totals may each scan a path of height h.
Space O(h + L) — the current path uses h slots and the saved totals use one slot
per leaf, L.
Subtract while descending — make the leaf answer local
When you enter a node, subtract its value from the remaining target. At a leaf, the route matches exactly when that remainder is zero. Otherwise, pass the smaller question to both children.
def has_path_sum(root: TreeNode | None, target_sum: int) -> bool:
if root is None:
return False
remaining = target_sum - root.val
if root.left is None and root.right is None:
return remaining == 0
return (
has_path_sum(root.left, remaining)
or has_path_sum(root.right, remaining)
)The leaf check prevents the classic false positive: matching the target at an internal
node and stopping before the route is complete. The or also short-circuits as soon as
one finished route matches.
Time O(n) — each node is visited at most once. Space O(h) — recursion holds one root-to-leaf route.
Python's call stack may fail on the valid 1,200-node line in the hidden suite. Keep the same remaining-target state in an explicit stack when depth is untrusted:
def has_path_sum_iterative(root: TreeNode | None, target_sum: int) -> bool:
if root is None:
return False
stack = [(root, target_sum - root.val)]
while stack:
node, remaining = stack.pop()
if node.left is None and node.right is None and remaining == 0:
return True
if node.left is not None:
stack.append((node.left, remaining - node.left.val))
if node.right is not None:
stack.append((node.right, remaining - node.right.val))
return FalseThat version keeps O(n) time and O(h) space without depending on Python's recursion limit.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
true
Run: visible + custom · Submit: full suite