Return true if the tree has a root-to-leaf path whose node values sum to target.
hasPathSum(root, target)
Input format: tree | target (level-order tree with x for missing children). An
empty tree has no path.
(5 4 8 11 x 13 4 7 2), target=22 // → true (5→4→11→2)
(1 2 3), target=5 // → false
(empty), target=0 // → false
This is about root-to-leaf paths — a naturally recursive, tree-shaped structure. Whenever a question is about root-to-leaf paths, ask: can I reformulate it as the same question on a smaller subtree? That's the hallmark of a recursion-friendly problem.
At the root: does some root-to-leaf path sum to target? Standing at a node partway down, having already accounted for its ancestors' values, the remaining values must sum to some remaining target — starting as the original target and shrinking as you descend. At any node: does some path from here to a leaf sum to the remaining target?
Same shape of question, just rooted differently with an adjusted target — subtract the current node's value as you step in, and ask the same question of its children.
Two situations end the recursion:
At a non-leaf node, a valid root-to-leaf path goes through either child. The node succeeds if either subtree, given the reduced target, finds a valid path — a logical OR of the two recursive calls.
Every node is visited at most once, O(1) work each — O(n) time overall. Recursion depth is bounded by tree height — O(h) space. Far better than enumerating all root-to-leaf paths explicitly and checking sums afterward; this never materializes a path, just carries the remaining target down through the calls.
def has_path_sum(root, target):
if root is None:
return False
if root.left is None and root.right is None:
return target == root.val
rest = target - root.val
return has_path_sum(root.left, rest) or has_path_sum(root.right, rest)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.