All Paths for a Sum (Collect Every Root-to-Leaf Path Matching a Target)

• All Paths for a Sum extends the single-boolean path-sum check into a collection problem that returns every qualifying path.
• Running path list tracks the current root-to-node sequence; each node is appended on entry and removed on exit.
• Backtracking means the add-then-remove discipline that lets one mutable list serve every branch of the tree.
• Defensive copy at a matching leaf stores new ArrayList<>(currentPath) so the live list can keep changing safely.
• Time is O(n) to visit plus O(h) per qualifying leaf to copy, giving O(n * h) worst case.
• Space is O(h) for the stack plus the size of all stored paths.

What is the All Paths for a Sum problem?

All Paths for a Sum asks you to find every root-to-leaf path in a binary tree where the node values along the path add up to a given target. Unlike the simpler Path Sum problem that returns only true or false, this variant must return the actual paths. The approach is a depth-first traversal that carries a mutable list representing the current path, copies it whenever a leaf matches the target, and backtracks by removing the last element after exploring both children.

package com.bank.service;

import java.util.ArrayList;
import java.util.List;

public class ApprovalPathFinder {
    // Entry point: find all root-to-leaf paths summing to target
    public List<List<Integer>> findAllPaths(TreeNode root, int target) {
        List<List<Integer>> results = new ArrayList<>();
        dfs(root, target, new ArrayList<>(), results);
        return results;
    }
}

Why does this problem exist?

In real banking systems, a loan approval flows through multiple desks, each charging a fee. The compliance team sometimes needs every chain of desks whose total fees match a specific budget figure, not just whether one exists. This is exactly the collection version of path sum: enumerate all qualifying paths rather than stop at the first.

How does backtracking work internally?

Backtracking is the add-then-remove discipline on a single mutable list. When you enter a node, you append it to the path. When you leave a node after exploring both children, you remove the last element. This means the list always reflects the current root-to-node path, and you never allocate a fresh list at every recursive call.

private void dfs(TreeNode node, int remaining,
                 List<Integer> currentPath,
                 List<List<Integer>> results) {
    if (node == null) return;

    currentPath.add(node.val);  // Step 1: add current node

    // Step 2: check if this is a matching leaf
    if (node.left == null && node.right == null
            && remaining == node.val) {
        results.add(new ArrayList<>(currentPath)); // defensive copy
    }

    // Step 3: recurse into children with reduced target
    dfs(node.left, remaining - node.val, currentPath, results);
    dfs(node.right, remaining - node.val, currentPath, results);

    // Step 4: backtrack by removing the current node
    currentPath.remove(currentPath.size() - 1);
}

Example tree:       5
                   / \
                  4    8
                 /    / \
                11   13   4
               / \       / \
              7   2     5   1

Target = 22
Paths found: [5,4,11,2] and [5,8,4,5]

Why must you store a defensive copy?

The most common bug in this pattern is storing the live list reference instead of a copy. Because the live list keeps changing as backtracking continues, every stored reference would end up pointing at the same eventually-empty list. The fix is new ArrayList<>(currentPath) at every matching leaf.

// WRONG: stores the live reference
results.add(currentPath);  // all entries point to same list

// CORRECT: stores a snapshot
results.add(new ArrayList<>(currentPath));  // each entry is independent

What is the time and space complexity?

Each node is visited exactly once during the DFS, which is O(n). However, at every matching leaf you copy the current path, which has length up to h (the tree height). In the worst case there can be O(n) leaves, so the total copying cost is O(n * h). For a balanced tree h is O(log n), and for a skewed tree h is O(n), giving O(n^2) in the worst case.

• The space breaks down as:
• O(h) for the recursion call stack.
• O(h) for the running path list.
• O(k * h) for the k result paths stored.

// Banking example: model approval desks with BigDecimal fees
package com.bank.model;

import java.math.BigDecimal;

public class ApprovalDesk {
    public String deskName;
    public BigDecimal fee;
    public ApprovalDesk left;
    public ApprovalDesk right;

    public ApprovalDesk(String name, BigDecimal fee) {
        this.deskName = name;
        this.fee = fee;
    }
}

How is this different from Path Sum (boolean version)?

Path Sum returns true or false and short-circuits on the first match. All Paths for a Sum must explore every branch because multiple qualifying paths can exist. Path Sum needs no path list and no copying; All Paths for a Sum needs both.

| Aspect | Path Sum (boolean) | All Paths for a Sum |
|--------|-------------------|--------------------|
| Return type | boolean | List of Lists |
| Short-circuit | Yes, on first match | No, must explore all |
| Path tracking | Not needed | Running list + backtrack |
| Defensive copy | Not needed | Required at each match |
| Time | O(n) | O(n * h) worst case |

What are common mistakes?

The first mistake is forgetting the defensive copy, as discussed above. The second mistake is adding the node value to the path instead of the node itself when the problem asks for node values. The third mistake is checking the sum condition at every node instead of only at leaves, which would report prefix paths that do not reach a leaf.

// WRONG: checks at every node, not just leaves
if (remaining == node.val) {
    results.add(new ArrayList<>(currentPath));
}

// CORRECT: checks only at leaf nodes
if (node.left == null && node.right == null && remaining == node.val) {
    results.add(new ArrayList<>(currentPath));
}

What about iterative approaches?

You can replace the recursion with an explicit stack that stores tuples of (node, remaining target, path snapshot). However, because you must copy the path at each stack push, this approach uses more memory than the backtracking version that reuses one list. The recursive backtracking solution is preferred unless the tree is extremely deep and risks a stack overflow.

What are edge cases?

• An empty tree returns an empty list of paths.
• A single-node tree where the node value equals the target returns a list containing one path with that single value.
• A tree where no path matches returns an empty list.
• Negative node values are valid and the algorithm handles them without changes because it subtracts each value from the remaining target.

// Edge case: single node tree
//   Target = 5, Tree = [5]
//   Result: [[5]]

// Edge case: no matching path
//   Target = 100, Tree = [1,2,3]
//   Result: []

What should a senior engineer know?

The total work is not linear when many paths qualify. Copying a path costs O(h) and there can be O(n) leaves, so the worst-case cost is O(n * h). For a balanced binary tree this is O(n log n), and for a skewed tree it is O(n^2). This cost is inherent to producing the paths themselves. If you only need the count of qualifying paths rather than the paths themselves, you can avoid the copying cost entirely and solve it in O(n).

Another senior point is that in production systems like the National Bank of India audit service, Rajesh would stream the qualifying paths rather than collecting them all in memory, using a callback or an iterator pattern, to avoid holding O(k * h) paths in the heap simultaneously.