Path Sum II — LC 113 DFS Backtracking All Root to Leaf Paths

Problem Statement#

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths whose node values sum to targetSum. A leaf is a node with no children.

Constraints:

• Number of nodes is in range 0 to 5000
• Node values are in range -1000 to 1000
• targetSum fits in 32-bit signed integer

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

Input:  root = [1,2,3], targetSum = 5
Output: []

Why This Problem Matters#

LeetCode 113 Path Sum II is a Medium that recurs in Amazon, Meta, Microsoft, and Bloomberg interviews. It is the canonical introduction to DFS with backtracking on trees — append on entry, pop on exit. After this pattern clicks, problems like LC 257 Binary Tree Paths, LC 437 Path Sum III, and LC 124 Binary Tree Maximum Path Sum become straightforward variations.

The problem tests two things: correct leaf detection and correct path snapshotting. Many candidates accidentally append the path reference instead of a copy, so all entries in the result alias the same list and end up empty after final backtracking. Others miss the leaf condition (not node.left and not node.right) and accept partial paths that happen to sum to target.

For senior loops, interviewers ask the follow-up "what if values can be negative?" — which makes prefix-sum optimization tricky, and forces candidates to rely on full DFS exploration without early pruning.

The Core Insight#

Every root-to-leaf path is a unique sequence. To enumerate all such paths and filter by sum, we DFS from the root carrying a mutable path list and a remaining target. At each node:

1. Append the node's value to path and subtract from remaining.
2. If the node is a leaf and remaining == 0, snapshot path into the result.
3. Recurse left and right.
4. Pop the node's value from path so siblings start with the correct state.

The append-pop discipline is backtracking. The snapshot must be a copy (path[:] in Python, [...path] in JavaScript) — otherwise all result entries reference the same list and become empty after the final pop.

Visual Dry Run#

Tree: 5 -> {4 -> {11 -> {7, 2}}, 8 -> {13, 4 -> {5, 1}}}, target = 22.

Snapshots are copies; the live path keeps mutating.

Solution (Optimal)#

class Solution:
    def pathSum(self, root, targetSum):
        result = []
 
        def dfs(node, remaining, path):
            if not node:
                return
            path.append(node.val)
            remaining -= node.val
            if not node.left and not node.right and remaining == 0:
                result.append(path[:])
            else:
                dfs(node.left, remaining, path)
                dfs(node.right, remaining, path)
            path.pop()
 
        dfs(root, targetSum, [])
        return result

var pathSum = function(root, targetSum) {
    const result = [];
 
    const dfs = (node, remaining, path) => {
        if (!node) return;
        path.push(node.val);
        remaining -= node.val;
        if (!node.left && !node.right && remaining === 0) {
            result.push([...path]);
        } else {
            dfs(node.left, remaining, path);
            dfs(node.right, remaining, path);
        }
        path.pop();
    };
 
    dfs(root, targetSum, []);
    return result;
};

Time: O(n^2) worst case — n nodes, each leaf may trigger a path copy of length up to h, and in a balanced tree there are n/2 leaves contributing O(n log n); skewed gives O(n^2). Space: O(h) for recursion plus O(n*h) for the result in the worst case.

Common Mistakes#

• Appending path instead of path[:] to result — every entry shares one list and becomes empty after final pop
• Missing the leaf check not node.left and not node.right and accepting partial paths
• Forgetting to pop on the failure branch, corrupting sibling exploration
• Using remaining == node.val before subtracting can be correct but mixing the two styles introduces bugs
• Returning early on negative remaining — wrong, because negative values may bring the sum back to target

Interview Tips#

• State the backtracking invariant explicitly: "I append on enter, pop on exit, snapshot only at leaves with remaining zero"
• Discuss the path-copy cost — explain why O(n^2) is the right worst-case bound
• Mention LC 437 Path Sum III as the natural follow-up using prefix sums
• For very deep trees, mention iterative DFS with an explicit stack to avoid recursion limits

Follow-up Questions#

• Negative values allowed (already supported, but ask about pruning) — no early pruning is safe
• Count paths instead of returning them — replace snapshot with count += 1, drop the path list
• Any-node-to-any-node paths summing to target — that is LC 437 with prefix sums
• Maximum path sum from root to leaf — track running max instead of comparing to target

Key Takeaways#

• LeetCode 113 Path Sum II is Medium and a top backtracking-on-trees problem at Amazon, Meta, Microsoft, and Bloomberg
• Time complexity is O(n^2) in the worst case due to path copies; space is O(h) recursion plus result size
• Pattern: DFS, append on enter, pop on exit, snapshot only at leaves with remaining equal to zero
• Always copy the path (path[:] or [...path]) when storing — never store the live reference
• Negative node values mean no early pruning is safe; explore the full tree
• This template generalizes to LC 257 Binary Tree Paths, LC 437 Path Sum III, and LC 124 Maximum Path Sum
• Leaf is defined as a node where both children are null, not where the sum first reaches target