LeetCode Path Sum: DFS With a Running Total

LeetCode 112 — 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.

Brute Force

Collect every root-to-leaf path as a list, sum each one, and check. Correct but throws away the streaming nature of DFS.

def hasPathSum(root, targetSum):
    paths = []
    def walk(node, acc):
        if not node:
            return
        acc = acc + [node.val]
        if not node.left and not node.right:
            paths.append(acc)
            return
        walk(node.left, acc)
        walk(node.right, acc)
    walk(root, [])
    return any(sum(p) == targetSum for p in paths)

The allocations are wasteful and the final sum loops over each path again.

Optimal Solution

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.

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))

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.

Walk Through an Example

Take this tree and target 22:

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

DFS down 5 -> 4 -> 11 -> 2 leaves remaining 22 - 5 - 4 - 11 - 2 = 0. Node 2 is a leaf, and node.val == 0 is false because 2 is not 0 — wait, that needs more care. Let’s redo: at node 2 we check node.val == remainingTargetAtParent. 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.

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

• LeetCode 113 — Path Sum II (collect every matching path)
• LeetCode 437 — Path Sum III (paths need not start at root)
• LeetCode 129 — Sum Root to Leaf Numbers
• LeetCode 124 — 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 — and your interview conversation moves from “can you write DFS?” to “how would you optimize it?”.