🛤

Tree Path Problems — Root-to-Leaf & Any-Node Paths

Two complementary patterns: backtracking DFS tracks the current path from root to leaf, adding/removing nodes as you descend and backtrack. Max-gain DFS uses bottom-up return values to evaluate paths passing through any node — the global answer is updated at each step while the return value propagates only the best single branch upward.

🛤 Root-to-Leaf Backtracking 📈 Max Path (Any Node) 🔄 Post-order Bottom-up Time O(n) Space O(h)

📋 When to Use

Path Sum / Path Sum II — backtrack DFS, carry remaining sum down
Sum Root to Leaf Numbers — multiply accumulated value × 10 + digit
Count paths with target sum — prefix sum + hashmap (Path Sum III)
Max path sum (any node) — post-order gain, discard negatives
Good nodes count — carry max-so-far down the path

💡 Key distinction: root-to-leaf paths use explicit path.add / path.remove (backtracking). Any-node paths never store the path — they compute a gain value bottom-up and update a global ans via L + R + node.val.

⚡ Complexity

Time

O(n)

Space (stack)

O(h)

Where n = number of nodes, h = tree height.
Balanced tree: O(log n) stack depth.
Skewed tree: O(n) stack depth.
Path Sum II also uses O(h) for the current path list — worst case O(n) if all nodes form the path.
Every node visited exactly once: O(n) time.

Problem Given a binary tree [root=5, left=4→11→(7,2), right=8→(13, 4→5)] and targetSum = 22, find all root-to-leaf paths whose node values sum to the target. Backtracking DFS: carry remaining sum down, add to path list, undo on return.
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,5], targetSum = 22 · Answer: [[5,4,11,2],[5,8,4,5]]

Step 0 / 12

🔍 Init ⬇ Descend 🍃 Visit Leaf ✅ Found! ↩ Backtrack 🏁 Done

🛤 Path Sum II backtracking — tree has target=22. We descend, building a path list. At each leaf we check if remaining sum == 0. We backtrack by removing the last element.

// dfs(node, rem=22, path=[]) — path sum backtracking

🌲 Tree (target = 22)

on path

found!

dead end

default

🛤 Current Path

[ empty ]

rem 22 / target 22

✅ Found Paths

— none yet —

📝 Result:

[ waiting... ]

🧩 Pattern Skeleton Java 8

// ─── Root-to-Leaf Paths (Path Sum II) ────────────────
List<List<Integer>> result = new ArrayList<>();

void dfs(TreeNode n, int rem, List<Integer> path) {
    if (n == null) return;
    path.add(n.val);                              // add to path
    if (n.left == null && n.right == null && rem == n.val)
        result.add(new ArrayList<>(path));        // found path
    dfs(n.left,  rem - n.val, path);
    dfs(n.right, rem - n.val, path);
    path.remove(path.size() - 1);               // backtrack
}

// ─── Max Path Sum (any node to any node) ─────────────
int ans = Integer.MIN_VALUE;

int maxGain(TreeNode n) {
    if (n == null) return 0;
    int L = Math.max(0, maxGain(n.left));        // discard negatives
    int R = Math.max(0, maxGain(n.right));
    ans = Math.max(ans, L + R + n.val);          // path through n
    return Math.max(L, R) + n.val;               // contribute upward
}

🎯 Practice Problems

#112 Path Sum 🛤 root-to-leaf, rem==0 at leaf Easy #113 Path Sum II 🛤 backtrack, collect all paths Medium #129 Sum Root to Leaf Numbers 🛤 carry cur = cur*10 + val Medium #124 Binary Tree Maximum Path Sum 📈 maxGain, ans=L+R+val Hard #437 Path Sum III 🔑 prefix sum + hashmap Medium #1448 Count Good Nodes in Binary Tree 🛤 carry maxSoFar down path Medium