Does a root-to-leaf route add up to a target?

Subtract each node's value from the target on the way down. At a leaf, the route works if what is left is zero. Return True as soon as any branch succeeds. O(n) time, O(h) stack.

The 'leaf' condition matters: a node with one child is not the end of a route.

Passing the remaining target down is cleaner than building route totals on the way up.

To list all routes, carry the route as a list and copy it at each leaf (backtracking).

def route_hits(root: Node | None, target: int) -> bool:
    if root is None:
        return False
    left = target - root.val
    if not (root.left or root.right):
        return left == 0  # a leaf: the route ends here
    return route_hits(root.left, left) or route_hits(root.right, left)

Common mistakes

• Stopping at a node with one missing child, treating it as a leaf.
• Returning True for an empty tree with target 0; usually the answer is False.

Mention the leaf condition before you code; it is the edge case interviewers watch for.

Follow-up questions

Think of your answer first, then open the hint.

1. How would you count routes that start and end anywhere going down?

   Show hint

   Prefix sums along the current route with a hash map, O(n).

2. What about negative values?

   Show hint

   This solution still works; you cannot prune early when the total passes the target.