Path Sum (LeetCode 112)

The problem

You get the root of a binary tree and an integer target. Return True if some path from the root down to a leaf has node values that add up to exactly target. A leaf is a node with no children.

Input:  root = [5,4,8,11,null,13,4,7,2,null,null,null,1], target = 22

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

Output: True

The path 5 → 4 → 11 → 2 adds up to 22.

How to think about it

Start with brute force. Collect every root-to-leaf path into a list, sum each one, and check whether any equals the target. That’s O(n) paths of up to O(h) length each, plus the memory to store them. You don’t need the paths themselves, only their sums.

The key insight: carry the remaining amount down instead of the path. When you step from a node to its child, the child’s subtree must make up target - node.val. So pass the remainder down. At a leaf, the question collapses to one comparison: is the remainder exactly this leaf’s value?

Stop at leaves, not at None. It’s tempting to check target == 0 when you reach an empty child. That’s wrong: a node with only one child would let you “finish” through its missing side, which isn’t a leaf. Checking at real leaves keeps the definition honest.

Which pattern is this? Tree DFS where state flows down (the remaining sum) and a boolean flows up (found or not). The tell is “root-to-leaf path” plus a condition on its values.

Approach

1. If the node is empty, return False (no path through nothing).
2. If the node is a leaf, return whether target == node.val.
3. Otherwise compute rem = target - node.val.
4. Return whether the left subtree or the right subtree has a path summing to rem.

The or short-circuits, so the search stops as soon as one path works.

Solution

def has_path_sum(root, target):
    if not root: return False
    if not root.left and not root.right: return target == root.val   # leaf: does it finish the sum?
    rem = target - root.val                                          # what the rest of the path must add up to
    return has_path_sum(root.left, rem) or has_path_sum(root.right, rem)
# has_path_sum(tree[5,4,8,11,null,13,4,7,2,null,null,null,1], 22) -> True

Dry run

On the example with target = 22, following the calls until the answer is found:

The right half of the tree is never explored, because or already has a True.

Complexity

• Time: O(n). In the worst case (no valid path) every node is visited once.
• Space: O(h). The recursion stack is as deep as the tree height: O(log n) balanced, O(n) skewed.

Edge cases and pitfalls

• Empty tree returns False, even when target is 0. There is no path at all.
• Paths must end at a leaf. For [1, 2] with target = 1, the answer is False: node 1 has a child, so it’s not a leaf.
• Negative values are allowed, so you can’t prune when the running sum passes the target. [-2, null, -3] with target = -5 is True.
• Don’t test at None children. That’s the most common wrong version, and it accepts paths that stop at a one-child node.

Related problems

• Binary Tree Maximum Path Sum (LeetCode 124): any path, not just root-to-leaf, and you maximise instead of match.
• Maximum Depth of Binary Tree (LeetCode 104): the same DFS skeleton returning a number.
• Validate Binary Search Tree (LeetCode 98): another problem where state (a range) is passed down.