Exercise 4: Path Sum 🎯

Your Task

Write a function has_path_sum(root, target) that returns True if the tree has a root-to-leaf path where all the values add up to target.

A leaf is a node with no left or right child.

---

Examples

#         5
#        / \
#       4   8
#      /   / \
#     11  13   4
#    /  \       \
#   7    2       1

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.right.left = TreeNode(13)
root.right.right = TreeNode(4)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
root.right.right.right = TreeNode(1)

print(has_path_sum(root, 22))  # True  (path: 5 → 4 → 11 → 2)
print(has_path_sum(root, 26))  # True  (path: 5 → 8 → 13)
print(has_path_sum(root, 100)) # False

print(has_path_sum(None, 0))  # False

#   1
#  / \
# 2   3

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

print(has_path_sum(root, 1))  # False  (leaf paths are 1+2=3, 1+3=4)

---

Expected Complexity

	Complexity
Time	O(n) — may visit every node
Space	O(h) — recursion stack depth

---

Approach

A clever trick: instead of tracking the running sum, subtract the current node's value from the target as you go deeper.

1. Base case (null): return False
2. Base case (leaf): return True if node.val == target (used up exactly!)
3. Subtract node.val from target, then check left or right subtree

---

Hints