Path Sum — DFS With a Running Target

Path Sum looks like a checkbox question and is exactly that, but the family of follow-ups it spawns (Path Sum II, Path Sum III, Sum Root to Leaf Numbers) leans on the same primitive. Get the leaf condition right once and you own the whole cluster.

The Problem

Given the root of a binary tree and an integer targetSum, return true if any root-to-leaf path has values summing to targetSum. A leaf is a node with no children. An empty tree returns false regardless of target.

Intuition

Subtract as you descend. Pass the remaining target down through the recursion. When you reach a leaf, check whether the remainder equals the leaf’s value. The two-condition leaf check — “no left child and no right child” — is what people forget. A node with one missing child is not a leaf, and treating it as one produces phantom paths that end in midair.

Explanation with Example

Take this tree and target 22:

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

DFS down 5 -> 4 -> 11 -> 2. The remaining target when we entered node 2 was 22 - 5 - 4 - 11 = 2. And node.val = 2. Match. Return true.

Phrasing the check this way — compare the leaf’s value to the inherited remainder — avoids off-by-one mistakes around when you subtract.

target = 22
      5    remaining for children: 22 - 5 = 17
     / \
    4   8        17 - 4 = 13       17 - 8 = 9
   /   / \
  11  13  4      13 - 11 = 2
 /  \      \
7    2      1    at leaf 2: node.val (2) == remaining (2)  MATCH

path: 5 -> 4 -> 11 -> 2  sums to 22  ===> return True

Code

def hasPathSum(root, targetSum):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == targetSum
    remaining = targetSum - root.val
    return (hasPathSum(root.left, remaining) or
            hasPathSum(root.right, remaining))

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == targetSum;
    int remaining = targetSum - root.val;
    return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    if (!root->left && !root->right) return root->val == targetSum;
    int remaining = targetSum - root->val;
    return hasPathSum(root->left, remaining) || hasPathSum(root->right, remaining);
}

Edge Cases

• Empty tree — return false even if targetSum is 0. There is no root-to-leaf path in an empty tree.
• Negative values — fine. The arithmetic is the same.
• A single-node tree where the value equals the target — return true.
• A node with one child — keep descending; only check the target at true leaves.
• Very deep skewed trees — switch to an iterative DFS if recursion depth is a concern.

Complexity Analysis

Time is O(n) because every node is visited at most once. Space is O(h) for recursion. The brute-force version is O(n) for traversal but O(n) for the path list and another O(n) summed across leaves, so it scales worse in practice.

For why “O(n) time, O(h) space” is the bread-and-butter budget of tree DFS, see Big-O Notation Explained.

How to Explain It in an Interview

Start by defining a leaf carefully. State the recurrence: “true if and only if there is a root-to-leaf path whose values sum to targetSum, equivalent to a left-or-right subtree path summing to targetSum - root.val.” Then write the function in two lines after the leaf check. If asked about iterative, swap to an explicit stack of (node, remaining) pairs — the logic is identical.

If the interviewer pushes toward Path Sum II, mention you would append to a path list and use backtracking on the way back up. If toward Path Sum III, mention the prefix-sum hash map trick that converts it into a one-pass problem — there is a strong link to the hash map post.

Related Problems

• Path Sum II (collect every matching path)
• Path Sum III (paths need not start at root)
• Sum Root to Leaf Numbers
• Binary Tree Maximum Path Sum

The last one steps up to allow any-node-to-any-node paths and is a different beast — it requires post-order accounting.

Wrap up

Path Sum is the prototype DFS-with-accumulator problem. Lock in three things: how to recognize a leaf, when to subtract, and how to early-exit on or. Once these reflexes are automatic, the whole family of path problems collapses into variations on the same shape.