Path Sum: Threading State Down the Recursion

This one is a Easy-rated classic reported from Amazon, Meta, Oracle interviews: "Path Sum". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Tree DFS pattern on sight. Part 5 of 11 in the Tree DFS arc.

The Problem

Given a tree root and target_sum, return whether any root-to-leaf path sums to the target. Leaf means no children — and values can be negative, which quietly eliminates every early-exit shortcut based on the running sum exceeding the target.

Input:  root = [5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1], target = 22
Output: True
The path 5 -> 4 -> 11 -> 2 sums to 22.

Recognizing the Tree DFS Pattern

Depth-first search commits to one branch before trying siblings — recursion (or an explicit stack) whose call structure mirrors the tree itself. Its natural questions are about paths (root to leaf), subtree properties (computed bottom-up from children), and exhaustive exploration (islands, connected regions). The recurring design decision is what each recursive call returns versus what it accumulates in shared state.

Path-accumulated state with a decision at leaves is the state-threading form of DFS: pass the remaining target downward, and the leaf check becomes a comparison against the leaf's own value. Downward state, leaf decision — a shape worth naming because harder problems (Path Sum II and III) reuse it.

The Approach

Recurse with target - node.val. At a leaf, return whether the remaining target equals the leaf value. An empty child contributes False, and the two-child case is an OR of the recursions.

The subtle base case: an empty tree has no paths, so target 0 on an empty tree is False — encode it as if not root: return False, and mention negative values when tempted to prune.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


def has_path_sum(root: TreeNode | None, target_sum: int) -> bool:
    """True if some root-to-leaf path sums to target_sum."""
    if root is None:
        return False
    remaining = target_sum - root.val
    if root.left is None and root.right is None:
        return remaining == 0
    return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)

Complexity

• Time: O(n) — worst case visits every node; OR short-circuits on success
• Space: O(h) — recursion stack

Interview Tips and Follow-Ups

• [1, 2] with target 1 is the planted case: the root alone is not a path — paths end at leaves. Volunteer it.
• Negative values are why you cannot prune on remaining < 0 — say it before writing any early return.
• The ladder: Path Sum II collects the paths (backtracking), Path Sum III counts any-to-any downward paths (prefix sums on paths). Know where each lives.

If this clicked, continue the Tree DFS arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.