Path Sum: Root-to-Leaf Target Check

You are given the root of a binary tree and a target sum. Return True if the tree has a root-to-leaf path where the node values add up to exactly the target sum.

This is LeetCode 112: Path Sum, and it is one of the cleanest examples of passing state down through a tree during a pre-order traversal. Instead of collecting results going back up (like Maximum Depth), you carry a shrinking remainder going down. When you hit a leaf, you check if the remainder hit zero.

Why this problem matters

If you have solved Maximum Depth of Binary Tree, you already know how to recurse through a tree and combine results on the way back up. Path Sum flips the direction. Here, the interesting work happens on the way down. You subtract each node's value from the target as you descend, and the check happens at the leaves.

This "pass state downward" approach is called pre-order state passing, and it shows up all over tree problems. Any time you need to track a running total, a path constraint, or a prefix condition as you walk from root to leaf, you are using this pattern.

The key insight

Instead of adding up all the values along a path and comparing to the target at the end, do it in reverse. Start with the full target and subtract each node's value as you go. When you reach a leaf, check if the remainder is exactly zero.

Why? Because subtraction lets you carry just one number (the remainder) instead of accumulating a list of values. It is simpler, uses no extra memory, and maps directly to a recursive call.

For the tree above with target 22:

• At node 5: remainder = 22 - 5 = 17
• At node 4: remainder = 17 - 4 = 13
• At node 11: remainder = 13 - 11 = 2
• At node 2: this is a leaf, and 2 - 2 = 0. Match!

The DFS solution

def has_path_sum(root, target_sum):
    if root is None:
        return False
    if root.left is None and root.right is None:
        return root.val == target_sum
    return (has_path_sum(root.left, target_sum - root.val) or
            has_path_sum(root.right, target_sum - root.val))

Let's break it down line by line:

• if root is None: return False is the null base case. If you fall off the tree (reached a null child), there is no path here. Return False.
• if root.left is None and root.right is None: checks whether the current node is a leaf. A leaf has no left child and no right child.
• return root.val == target_sum is the leaf check. At a leaf, the current node's value must exactly equal the remaining target. If it does, we found a valid path.
• The final return recurses into both children, subtracting the current node's value from the target. If either side finds a valid path, the or short-circuits and returns True.

Visual walkthrough

Let's trace the recursion through the tree with target sum 22. Watch how the remaining value shrinks at each level, and how the leaf check determines the result.

The key moment is Step 5. Node 2 is a leaf, and the remaining value is 2. Since 2 == 2, we found our match. True propagates all the way back up through the or at each level. The right subtree (node 8 and its children) never even needs to be explored because the or short-circuits once the left side returns True.

Why the null check matters

A common mistake is writing the leaf check like this:

# Wrong approach
def has_path_sum(root, target_sum):
    if root is None:
        return target_sum == 0  # Bug!
    return (has_path_sum(root.left, target_sum - root.val) or
            has_path_sum(root.right, target_sum - root.val))

This looks cleaner, but it is wrong. Consider a node that has a left child but no right child. When you recurse into the missing right child, root is None and target_sum might happen to be 0. The function returns True, but you did not actually reach a leaf. You stopped at a null pointer hanging off an internal node.

The correct version explicitly checks for leaves (both children are None) and only tests the condition there. Null nodes always return False.

Complexity analysis

Time is O(n) in the worst case. You might need to visit every node if no valid path exists, or if the valid path is the last one you check.

Space is O(h) where h is the height of the tree. That is the maximum depth of the recursion stack. For a balanced tree, h = log n. For a completely skewed tree (looks like a linked list), h = n.

In the best case, the function finds a valid path early and short-circuits via the or, skipping large portions of the tree. But we measure worst-case complexity, so it is still O(n) time.

Edge cases to watch for

• Empty tree (root is None): return False. There are no paths at all, so no path can sum to the target.
• Single node (leaf is the root): return root.val == target_sum. The root is both the start and end of the only path.
• Target sum is 0: still works. You need a root-to-leaf path where all values cancel out to zero.
• Negative node values: the algorithm handles them naturally. Subtracting a negative number increases the remainder.
• One-sided tree (every node has exactly one child): there is only one root-to-leaf path. The recursion follows it all the way down.

The building blocks

This problem is built on one fundamental building block:

Pre-order state passing (pre-order-state-passing). You pass a value (the remaining target) from parent to child during the recursive descent. At each node, you transform the state (subtract the node value) before passing it to the children. The check happens at the leaves. The skeleton looks like this:

def solve(node, state):
    if node is None:
        return BASE_RESULT
    state = TRANSFORM(state, node)
    if IS_LEAF(node):
        return CHECK(state)
    return COMBINE(solve(node.left, state), solve(node.right, state))

For path sum, TRANSFORM is target - node.val, CHECK is state == 0 (equivalently, node.val == remaining), and COMBINE is left or right.

This same pre-order state passing pattern appears in:

• Path Sum II (LeetCode 113): same traversal, but you collect all valid paths instead of returning a boolean. COMBINE appends to a list instead of using or.
• Sum Root to Leaf Numbers (LeetCode 129): the state is a running number formed by the digits. TRANSFORM is state * 10 + node.val, and at leaves you return the number.
• Binary Tree Paths (LeetCode 257): the state is a string path. You build the path going down and collect results at leaves.

Once you recognize the pre-order state passing skeleton, all of these problems become variations on the same theme.

From understanding to recall

You just traced through a clean recursive solution and watched the remainder shrink from 22 down to 0. You understand why you check at the leaf instead of at null, and why the or propagates True back up the tree. It all clicks right now.

But when you see Path Sum II or Sum Root to Leaf Numbers in an interview, will you instinctively reach for the pre-order state passing pattern? Will you remember to check at the leaf and not at the null node? Or will you fumble with the base case and lose five minutes debugging?

Understanding and recall are different skills. You understood the solution. Recall means you can produce it from scratch under pressure.

Spaced repetition builds recall. You practice typing the solution from memory at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the null base case, the leaf check, and the recursive subtraction from scratch. After a few repetitions, the pre-order state passing pattern is automatic.

Pre-order state passing is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Maximum Depth of Binary Tree - The foundational tree recursion problem. If Path Sum is about passing state down, Maximum Depth is about collecting results going back up. Learn both to see the full picture.
• Diameter of Binary Tree - Another tree DFS that combines local returns with a different concern (global max). Good for seeing how the same recursive skeleton adapts to different problems.