TreeMediumO(n²) time · O(n) space

Path Sum II

Mahabharata — All the Sacred Paths — Find Every Root-to-Leaf Path that Sums to Target

सभी पवित्र पथ — जो लक्ष्य तक पहुँचते। Backtrack: जोड़ो — आगे जाओ — वापस आओ॥

*All sacred paths — that reach the target. Backtrack: add — advance — remove.*

The Story

Find ALL root-to-leaf paths where the sum of node values equals targetSum.

For tree `[5,4,8,11,null,13,4,7,2,null,null,5,1]`, targetSum=22: [[5,4,11,2],[5,8,4,5]].

**Backtracking DFS:** ```java public List<List<Integer>> pathSum(TreeNode root, int targetSum) { List<List<Integer>> res = new ArrayList<>(); dfs(root, targetSum, new ArrayList<>(), res); return res; } void dfs(TreeNode root, int target, List<Integer> path, List<List<Integer>> res) { if (root == null) return; path.add(root.val); // Choose if (root.left == null && root.right == null && target == root.val) res.add(new ArrayList<>(path)); // Found a valid path! dfs(root.left, target - root.val, path, res); // Explore left dfs(root.right, target - root.val, path, res); // Explore right path.remove(path.size() - 1); // Unchoose (backtrack) } ```

The backtracking pattern: 1. **Add** root.val to path 2. **Check** at leaf: if target == root.val, add copy of path to result 3. **Recurse** on left and right with reduced target 4. **Remove** last element from path (backtrack)

Trace `[5,4,11,7,2]`, target=22: - path=[5]: dfs(4, 17) - path=[5,4]: dfs(11, 13) - path=[5,4,11]: dfs(7, 2) - path=[5,4,11,7]: leaf. 2==7? No. Remove 7. path=[5,4,11] - path=[5,4,11]: dfs(2, 2) - path=[5,4,11,2]: leaf. 2==2? Yes! Add copy. Remove 2. - Remove 11. path=[5,4] - Remove 4. path=[5] - Remove 5. Done.

The Same DFS (Already Optimal)

The backtracking DFS is already the standard solution. No simpler approach exists.

java

// Same backtracking — already optimal O(n²)
// O(n²) because copying each path to result takes O(path_length) ≈ O(n)

The Add-Check-Recurse-Remove Backtracking

path.add(val). At leaf with target==val: add copy to result. Recurse left and right with reduced target. path.remove(last). O(n) nodes, O(n) copy per result.

java

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(root, targetSum, new ArrayList<>(), res);
    return res;
}

void dfs(TreeNode root, int target, List<Integer> path, List<List<Integer>> res) {
    if (root == null) return;
    path.add(root.val);
    if (root.left == null && root.right == null && target == root.val)
        res.add(new ArrayList<>(path));
    dfs(root.left, target - root.val, path, res);
    dfs(root.right, target - root.val, path, res);
    path.remove(path.size() - 1);
}

Step-by-Step Walkthrough

Null root: return (no paths). ✅
Single leaf [1], target=1: path=[1]. Leaf: 1==1 → add [1]. Result=[[1]] ✅

Deep Insight

**Why new ArrayList<>(path) at result:** The path list is mutable and shared across the recursion. If we add `path` directly to `res`, future backtracking changes will corrupt the stored result. Always add a COPY.

**O(n²) time:** We visit n nodes. For each valid path of length h, we copy it (O(h)). In worst case (all paths valid), O(n × h) = O(n²) for a balanced tree.

**Path Sum I vs II:** tr-26 returns boolean (any path). tr-27 returns all paths. Same backtracking, but tr-27 stores the path and can't short-circuit.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(n)	n nodes × copying path O(h) at results
Optimal	O(n²)	O(n)	Same — unavoidable when storing all valid paths

Pattern Recognition

✅ All root-to-leaf paths: backtracking with path list
✅ Add at enter, remove at exit (backtrack)
✅ At leaf: check and add COPY of path
✅ O(n²) due to path copying

**LeetCode Trigger Phrases:**
→ "path sum II" — all root-to-leaf paths
→ Collect all paths matching target
→ Backtracking with path tracking

Bhagavad Gita 4.10

बहवो ज्ञानतपसा पूता मद्भावमागताः। रागद्वेषविमुक्तास्ते द्वन्द्वैर्विमुक्ताः सुखदुःखैः॥

Purified by the fire of knowledge and freed from attachment and aversion — many have come to My state, freed from the pairs of opposites.

Connection: Path Sum II reveals all the sacred paths — every root-to-leaf journey that reaches the exact target. Like the many souls who have followed different paths (yoga, knowledge, devotion) and yet each arrived at the same divine destination, the algorithm collects every valid path. Each path is unique in its route, yet each achieves the same goal: their total equals the target, the sacred sum.