Lesson 35 — Trees VIII: root-to-leaf paths

~20 minutes · Day 41 · tree DFS paths · Python

Tonight's problem is Path Sum. Interviewers like it because it tests a tree habit that feels small but matters everywhere: carry only the information the path still needs. You are not searching the whole tree at once. You are walking one root-to-leaf path at a time.

The invariant

Subtract the node's value as you descend; a path exists iff some leaf sees exactly zero remaining.

That's the whole move. A binary tree path in this problem must start at the root and end at a leaf. A leaf is a node with no children. So the recursive question is not “what is the total sum of this subtree?” It is: after using this node, how much sum is still missing on this one path?

A valid path is checked only at the leaf, after every node on that path has been subtracted.

Path Sum: the noisy way first

The brute force instinct is to build every root-to-leaf path, copy its values into a list, then sum each list at the end. That works, but it can cost O(nh): n nodes, path length up to height h, and repeated copying or summing of path values.

The better DFS keeps one number instead: remaining. At each node, subtract node.val. Only at a leaf do you ask whether the remaining sum is exactly zero.

def hasPathSum(root, targetSum):
    if root is None:
        return False                         # empty tree: no path
    remaining = targetSum - root.val         # use this node
    if root.left is None and root.right is None:
        return remaining == 0                # leaf decides
    return (
        hasPathSum(root.left, remaining) or  # try left path
        hasPathSum(root.right, remaining)    # try right path
    )

The final or matches the problem statement: one valid path is enough. Python's boolean operations also short-circuit, so if the left side finds a valid path, Python does not need to evaluate the right side.

Transfer: same pattern, new output

Suppose the question changed to: return one root-to-leaf path whose values sum to the target, or return an empty list if no such path exists.

Before opening the reveal: predict what still gets subtracted, and predict where the path is allowed to succeed. The invariant should not change.

def one_path(root, targetSum):
    if root is None:
        return []
    remaining = targetSum - root.val
    if root.left is None and root.right is None:
        return [root.val] if remaining == 0 else []
    left = one_path(root.left, remaining)
    if left:
        return [root.val] + left
    right = one_path(root.right, remaining)
    return [root.val] + right if right else []

What the trade buys you

The DFS visits each node once. The extra space is the recursion stack: one active call per level of tree height.

Practice — answer before you scroll past

remaining = targetSum - node.val
if remaining == 0:
    return True

Your move (tonight)

Solve Path Sum in your Notion tracker with the cycle — predict → attempt → compare → encode. In the predict step, say the brute force aloud first. In the attempt step, write the leaf check before the recursive calls. In the encode step, write the invariant at the top of this page in your own words.