Root To Leaf Target Sum
Problem
Given a binary tree and a target number, decide whether some path from the root down to a leaf has values adding up exactly to the target. A leaf is a node with no children, so a path must always end at the bottom of the tree. Values may be negative.
Examples
Input: tree = 5, left 4 with left child 11 having children 7 and 2,
right 8 with children 13 and 4; target = 22
Output: True
Why: the path 5, 4, 11, 2 adds up to 22Input: tree = 1 with a single left child 2; target = 1
Output: False
Why: the root is not a leaf, so the path cannot stop thereInput: tree = empty; target = 0
Output: False
Why: edge case, an empty tree has no root-to-leaf path at allHints
0 / 3
The tree splits the question into two smaller questions of the same kind, one per child, and the answer is yes when either of them says yes.
Rather than adding values up on the way back, subtract each value from the target as you descend, so a child only ever sees the amount still owed.
Descend from the root carrying the remaining amount. At a leaf, answer yes exactly when the remainder equals that leaf value. At an absent branch, answer no, so a one-child node is never mistaken for a stopping point.
Solution
Carrying the remaining amount downward turns the question at each node into the same question on a smaller tree, so one recursion covers the whole search. The absent-branch case must answer no rather than checking the remainder, otherwise a node with a single child would be treated as a valid endpoint. A leaf answers by comparing the remainder with its own value, and the two children are combined with a short-circuiting or. Time is O(n) in the worst case, and space is O(h) for the call stack.
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def has_path_sum(node, target):
if node is None:
return False # an absent branch is not a stopping point
rest = target - node.val
if node.left is None and node.right is None:
return rest == 0 # only a leaf may close the path
return has_path_sum(node.left, rest) or has_path_sum(node.right, rest)
print(has_path_sum(T(5, T(4, T(11, T(7), T(2))), T(8, T(13), T(4))), 22)) # -> True
print(has_path_sum(T(1, T(2)), 1)) # -> False
print(has_path_sum(None, 0)) # -> FalseStuck on the idea rather than the code? Path Sum Variants covers it.