Path Sum Problems Family, in depth: root-to-leaf checks, all paths, prefix-sum counting, maximum path sum and grid paths

The family at a glance

The numbers are the LeetCode problem numbers people know them by.

Here n is the number of nodes and h the height of the tree, which bounds both recursion depth and the length of every path you copy. A tree built from sorted input degenerates into a list with h equal to n.

First principles: which way does information flow?

Two constraints separate the variants: where a path may start and end, and whether it may change direction. Root-to-leaf paths start at the root and stop at a leaf, so a node only needs to know how much of the target its ancestors left. That is top-down state, passed as an argument.

A maximum path may start and end anywhere and bend once at its top node. No ancestor can know the answer in advance, so each node asks its children what the best straight path below them is worth, combines the answers, and reports one number upward. That is a bottom-up result, passed as a return value.

Mixing the directions, for example computing a bent path from a running sum passed down, is the usual way to pass the sample input and fail on a skewed tree.

Path Sum: one root-to-leaf check

Subtract each node's value from the target on the way down and ask, at each leaf, whether nothing is left. Two details carry the correctness. A leaf is a node with no children; checking the remainder at a null child would accept paths that stop at a one-child node in the middle of the tree. And the empty tree has no root-to-leaf path, so it returns false even for target 0.

def has_path_sum(root, target):
    """True if some root-to-leaf path adds up to target. Values may be negative."""
    if root is None:
        return False                      # the empty tree has no root-to-leaf path
    remaining = target - root.val
    if root.left is None and root.right is None:
        return remaining == 0             # decide only at a real leaf
    return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)


def has_path_sum_iter(root, target):
    """Same answer with an explicit stack: safe for trees deeper than the recursion limit."""
    stack = [(root, 0)] if root else []
    while stack:
        node, acc = stack.pop()
        acc += node.val
        if node.left is None and node.right is None and acc == target:
            return True
        if node.right:
            stack.append((node.right, acc))
        if node.left:
            stack.append((node.left, acc))
    return False

There is no early exit when the running sum exceeds the target: values can be negative, so a path that overshoots can come back. Prune only when values are known to be non-negative. The iterative version exists because CPython's default recursion limit is about 1,000 frames, and a tree built from 5,000 sorted keys overflows the recursive one.

Path Sum II: every path, with backtracking

To list the paths, carry the path itself down as well as the remaining target. This is the backtracking pattern from Backtracking, in depth: choose by appending the node, explore both children, unchoose by popping. One shared list is reused for the whole search, so memory stays at O(h) apart from the output.

def path_sum_all(root, target):
    out, path = [], []

    def dfs(node, remaining):
        if node is None:
            return
        path.append(node.val)                       # choose
        remaining -= node.val
        if node.left is None and node.right is None and remaining == 0:
            out.append(list(path))                  # record a COPY, not the live list
        else:
            dfs(node.left, remaining)               # explore
            dfs(node.right, remaining)
        path.pop()                                  # unchoose, on every exit path

    dfs(root, target)
    return out

The most frequent bug is appending path instead of list(path): every answer is then the same list object, which the final pops empty. The second is popping inside the else branch, so a matching leaf never removes itself and later paths are corrupted. The cost is dominated by copies: each matching path costs O(h) to copy and there can be up to one match per leaf, so the worst case is O(n h) time on top of the O(n) traversal.

Path Sum III: counting any downward path with prefix sums

Now a path may start at any node and end at any descendant, still moving downward. The brute force starts a walk at every node, which is O(n h): fine for balanced trees, quadratic for a list-shaped one. The linear solution borrows the subarray-sum trick. Along the path from the root, write the prefix sum after each node. A downward path from a node just below position i to position j sums to prefix[j] - prefix[i]. So the number of paths ending at the current node with sum target equals the number of earlier prefixes on the current root path equal to prefix - target. A hash map of prefix counts answers that in O(1) expected time; see hash tables for why.

from collections import defaultdict

def path_sum_count(root, target):
    """Count downward paths (any start, any end) whose values add up to target."""
    seen = defaultdict(int)
    seen[0] = 1                  # the empty prefix: lets a path start at the root

    def dfs(node, prefix):
        if node is None:
            return 0
        prefix += node.val
        found = seen[prefix - target]       # earlier prefixes on THIS root path
        seen[prefix] += 1
        found += dfs(node.left, prefix) + dfs(node.right, prefix)
        seen[prefix] -= 1                   # leave the branch: forget this prefix
        return found

    return dfs(root, 0)

Two lines make it correct. Seeding seen[0] = 1 represents the empty prefix before the root, so paths starting at the root are counted. Decrementing after both children return forgets the prefix when the search leaves the branch, so a left-subtree prefix is never matched by a right-subtree node.

Worked example: the diagram's tree with target 8. The prefixes on the path 10, 5, 3 are 10, 15, 18. At node 3 we look up 18 - 8 = 10, find the root's prefix once, and count the path 5, 3. At node 2 the prefix is 17; 9 is absent, so nothing is counted. Returning to the root removes 18, 17 and 15 from the map. At -3 the prefix is 7 and -1 is absent. At 11 the prefix is 18; 10 is present, so the path -3, 11 is counted. The answer is 2, and the prefix 15 from the left side was correctly unavailable to 11.

In Java, node values fit in int but a sum over a long path can exceed it, and silent overflow gives wrong counts rather than a crash. Use long for the prefix and a Map<Long, Integer> for the counts, seeded with 0L.

Maximum path sum: returning gains up

Here a path may be any sequence of connected nodes, at least one node long, and it may bend once at its highest node. Each node computes the best gain a straight path hanging below it can contribute, clamping negative child gains to 0 because a path is free not to go that way. It updates a global best with the bent path through itself, val + left + right, and returns the straight version, val + max(left, right), because a parent can extend only one side.

def max_path_sum(root):
    """Largest sum over any path of at least one node (may bend once at its top node)."""
    best = float("-inf")                    # NOT 0: an all-negative tree must return its max node

    def gain(node):
        nonlocal best
        if node is None:
            return 0
        left = max(gain(node.left), 0)      # a negative branch is simply not taken
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)    # path that bends here
        return node.val + max(left, right)           # parent may extend only one side

    gain(root)
    return best

Starting best at 0 returns 0 for a tree containing only -3, where the answer is -3. Worked example: for root -10 with left 9 and right 20, where 20 has children 15 and 7, node 20 returns 35 and records the bent path 15 + 20 + 7 = 42. The root sees gains 9 and 35, records 34 and returns 25. The answer, 42, never touches the root, which is why the global exists.

The grid variant: when the paths form a DAG

Minimum Path Sum asks for the cheapest route from the top-left to the bottom-right cell of a grid, moving only right or down. Routes share cells, so a tree-style search repeats work exponentially. The moves form a directed acyclic graph, so dynamic programming applies: the cost to reach a cell is its own cost plus the cheaper of the cells above and to the left, and one row of state is enough (see Dynamic programming, in depth).

def min_path_sum(grid):
    """Top-left to bottom-right, moving only right or down. Non-negative cells."""
    rows, cols = len(grid), len(grid[0])
    dp = [0] * cols
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                dp[c] = grid[0][0]
            elif r == 0:
                dp[c] = dp[c - 1] + grid[r][c]
            elif c == 0:
                dp[c] = dp[c] + grid[r][c]
            else:
                dp[c] = min(dp[c], dp[c - 1]) + grid[r][c]
    return dp[-1]

Allow moves in all four directions and the graph has cycles, the recurrence has no evaluation order, and the problem becomes Dijkstra's shortest path.

Failure modes

Operating the solutions: testing, depth and trade-offs

Test against a brute-force oracle on many small random trees: slow, obviously right, and with negatives and zeros it finds pruning, seeding and decrement bugs within a few hundred trials. random_tree and serialize are small helpers you write once.

import random

def brute_count(root, target):
    """O(n^2) oracle: start a walk at every node, count every prefix that matches."""
    def from_node(node, acc):
        if node is None:
            return 0
        acc += node.val
        return (acc == target) + from_node(node.left, acc) + from_node(node.right, acc)
    def every(node):
        if node is None:
            return 0
        return from_node(node, 0) + every(node.left) + every(node.right)
    return every(root)

for trial in range(2000):
    root = random_tree(size=random.randint(0, 12), lo=-5, hi=5)   # include negatives and zeros
    t = random.randint(-8, 8)
    assert path_sum_count(root, t) == brute_count(root, t), (serialize(root), t)

Depth is the operational constraint. For trees you did not build, such as parsed documents or file systems, assume depth and prefer an explicit stack, or cap depth with a clear error. Raising Python's recursion limit a lot moves the failure into the C stack, which can crash the process.

The trade-offs are memory for time. Prefix counting spends O(h) map entries to save a factor of h; Path Sum II's shared list saves allocation but every answer is a copy. For prefix sums over an array that changes, a Fenwick tree is the structure to reach for.

What to do next

1. Classify each new path question by where paths start and end and whether they bend; choose top-down state or bottom-up gains first.
2. Implement Path Sum I recursively and iteratively, and confirm the empty tree with target 0 returns false.
3. Implement Path Sum II and check that each recorded path is a copy and the pop runs on every exit.
4. Implement Path Sum III with a seeded, decremented prefix map and trace the worked example by hand.
5. Implement maximum path sum starting from negative infinity, and test a single-node tree with a negative value.
6. Write the brute-force oracle and run a few thousand random trees with negative values and zeros against every solution.
7. For Java, switch every running sum to long and add a test with a long path of large values.
8. Replace recursion with an explicit stack wherever the tree comes from outside your code.