Path Sum II: Backtracking With a Shared Path Buffer

"Path Sum II" is a Medium-level staple in Amazon, Meta, Bloomberg loops, and it is a textbook fit for the Tree DFS pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 6 of 11 in the Tree DFS arc.

The Problem

Return all root-to-leaf paths summing to the target, each as a list of values. The step up from Path Sum is state management: one shared path buffer, mutated on the way down and un-mutated on the way back — backtracking in its cleanest habitat.

Input:  root = [5, 4, 8, 11, None, 13, 4, 7, 2, None, None, 5, 1], target = 22
Output: [[5, 4, 11, 2], [5, 8, 4, 5]]

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.

Enumerate all X satisfying Y on a tree is DFS plus backtracking: the recursion explores, the shared buffer records the current path, and the pop after each recursive call restores the invariant that the buffer equals the path to the current node.

The Approach

Append the node value, recurse (or record a copy at a matching leaf), then pop. The pop is the backtrack — with it, one buffer serves every path; without it, paths bleed into each other. Copy on record (list(path)), because the buffer keeps mutating after the append.

Estimate output size when asked: a complete tree has n/2 leaves and paths of length log n, so output alone can be O(n log n) — the algorithm cannot beat its own output.

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 path_sum(root: TreeNode | None, target_sum: int) -> list[list[int]]:
    """All root-to-leaf paths summing to target_sum."""
    result: list[list[int]] = []
    path: list[int] = []

    def dfs(node: TreeNode | None, remaining: int) -> None:
        if node is None:
            return
        path.append(node.val)
        remaining -= node.val
        if node.left is None and node.right is None and remaining == 0:
            result.append(list(path))          # snapshot the shared buffer
        else:
            dfs(node.left, remaining)
            dfs(node.right, remaining)
        path.pop()                             # backtrack

    dfs(root, target_sum)
    return result

Complexity

• Time: O(n·h) — traversal is O(n); each matching leaf copies an O(h) path
• Space: O(h) — buffer plus recursion, excluding the output

Interview Tips and Follow-Ups

• The forgotten pop and the missing copy are the two ways this goes wrong — both produce plausible-looking garbage; test with two matching paths.
• Appending path itself (not a copy) makes every result alias one list — explain why the outputs all end up empty if asked to debug it.
• This append-recurse-pop skeleton is the same one behind Subsets and Permutations — tree backtracking and combinatorial backtracking are one pattern.

That wraps part 6 of the Tree DFS arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.