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.

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

Hints

💡 Hint 1 — Two Base Cases

You need two base cases:

root is None → return False (fell off the tree, never hit a leaf)
root is a leaf (root.left is None and root.right is None) → return root.val == target

💡 Hint 2 — Shrinking the Target

As you walk down, subtract the current node's value from target:

# After passing through this node, we need the remaining path
# to sum to (target - root.val)
remaining = target - root.val
return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)

💡 Hint 3 — How to Check for Leaf

A leaf node has no children:

is_leaf = root.left is None and root.right is None

✅ Solution

def has_path_sum(root, target):
    if root is None:
        return False

    # At a leaf: check if we've used up exactly the target
    if root.left is None and root.right is None:
        return root.val == target

    # Recurse: subtract current value, check both subtrees
    remaining = target - root.val
    return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)

Why this works: We start with the full target and "spend" each node's value as we go deeper. When we hit a leaf, we check if we've spent exactly the right amount. If either the left or right subtree has a valid path, we return True.

Path Sum