151. Path Sum II
š LeetCode Problem: 113. Path Sum II
š Difficulty: Medium
š·ļø Topics: Binary Trees, DFS, Backtracking, Path Tracking, Recursion
Problem Statement
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
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]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: []
Example 3:
Input: root = [1,2], targetSum = 0
Output: []
Constraints:
- The number of nodes in the tree is in the range [0, 5000]
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
š³ Visual Understanding - Finding Paths
What is a Root-to-Leaf Path?
Tree:
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Root-to-leaf paths:
1. [5, 4, 11, 7] ā sum = 27
2. [5, 4, 11, 2] ā sum = 22 ā
3. [5, 8, 13] ā sum = 26
4. [5, 8, 4, 5] ā sum = 22 ā
5. [5, 8, 4, 1] ā sum = 18
targetSum = 22
Answer: [[5,4,11,2], [5,8,4,5]]
Key Observations:
1. Must go from ROOT to LEAF
- Can't stop at internal node
- Can't start from middle
2. Need to track ENTIRE path
- Not just sum (like Problem 135)
- Need actual node values
3. Multiple paths possible
- Collect ALL valid paths
- Return as list of lists
This is Path Sum I + path collection! šÆ
Visual Path Exploration:
Exploring left side:
5
/
4
/
11
/ \
7 2
Path [5, 4, 11]:
Not a leaf! Continue...
Path [5, 4, 11, 7]:
Leaf! Sum = 27 ā 22 ā
Path [5, 4, 11, 2]:
Leaf! Sum = 22 = 22 ā
Add to result!
š§ The AHA Moment - Backtracking Pattern!
The Core Insight:
We need to:
1. Track current path as we go down
2. Check at leaves if sum matches
3. Collect valid paths
4. BACKTRACK to explore other paths
This is BACKTRACKING! šÆ
Build path going down
Check at leaf
Remove last when coming back up
Backtracking Visualization:
Tree:
5
/ \
4 8
State as we traverse:
Going down left:
path = [5]
path = [5, 4]
(explore children)
Coming back up:
path = [5, 4]
Remove 4: path = [5]
Going down right:
path = [5]
path = [5, 8]
(explore children)
Coming back up:
path = [5, 8]
Remove 8: path = [5]
Add before recurse, remove after recurse! š
Why Backtracking is Needed:
Without backtracking:
path = [5, 4, 11, 2]
(returns from this path)
path still = [5, 4, 11, 2]
Go to next path: [5, 4, 11, 2, 8, 13]
WRONG! ā
With backtracking:
path = [5, 4, 11, 2]
Remove 2: path = [5, 4, 11]
Remove 11: path = [5, 4]
Remove 4: path = [5]
Now can explore right: [5, 8]
CORRECT! ā
š§ Recursive Thinking - Building the Solution
Base Case:
When to check if path is valid?
ā At LEAF nodes
What's a leaf?
ā node.left == null && node.right == null
If at leaf:
Check: currentSum == targetSum?
If yes: Add path to result
Return
Recursive Case:
For any node:
STEP 1: Add current node to path
path.add(node.val)
STEP 2: Update remaining sum
remaining = targetSum - node.val
STEP 3: Check if leaf
if (leaf && remaining == 0):
result.add(new ArrayList<>(path)) // Copy path!
STEP 4: Recurse on children
if (node.left != null):
dfs(node.left, remaining, path, result)
if (node.right != null):
dfs(node.right, remaining, path, result)
STEP 5: BACKTRACK - Remove current node
path.remove(path.size() - 1)
What Each Node Does:
Each node:
1. Adds itself to path
2. Checks if it's a valid leaf
3. Explores children (if any)
4. Removes itself from path
Returns: Nothing (void)
- Result built up in result list
- Path modified by reference
šÆ Solution 1: DFS with Backtracking
Implementation:
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
// Start DFS from root
dfs(root, targetSum, path, result);
return result;
}
private void dfs(TreeNode node, int remaining,
List<Integer> path, List<List<Integer>> result) {
// Base case: null node
if (node == null) {
return;
}
// STEP 1: Add current node to path
// Building path as we go down
path.add(node.val);
// STEP 2: Check if this is a leaf with target sum
// CRITICAL: Must be LEAF (both children null)
if (node.left == null && node.right == null) {
// Check if sum matches
if (remaining == node.val) {
// Found valid path! Add copy to result
// WHY copy? Path will be modified later!
result.add(new ArrayList<>(path));
}
}
// STEP 3: Explore left subtree
// Pass remaining sum minus current node
if (node.left != null) {
dfs(node.left, remaining - node.val, path, result);
}
// STEP 4: Explore right subtree
// Pass remaining sum minus current node
if (node.right != null) {
dfs(node.right, remaining - node.val, path, result);
}
// STEP 5: BACKTRACK
// Remove current node from path
// WHY? Allow exploration of other paths!
path.remove(path.size() - 1);
}
}
Why New ArrayList When Adding to Result?
// ā WRONG - Adds reference
result.add(path);
// Problem: path will be modified!
// All entries in result point to same list
// Final result: [[empty], [empty], ...]
// ā CORRECT - Adds copy
result.add(new ArrayList<>(path));
// Creates snapshot of current path
// Immune to future modifications
// Each result entry is independent
šÆ Solution 2: Cleaner Version (No Null Checks)
Implementation:
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(root, targetSum, path, result);
return result;
}
private void dfs(TreeNode node, int remaining,
List<Integer> path, List<List<Integer>> result) {
// Base case: null node
if (node == null) {
return;
}
// Add current node to path
path.add(node.val);
// Leaf check and sum check together
if (node.left == null && node.right == null &&
remaining == node.val) {
result.add(new ArrayList<>(path));
}
// Recurse on both children (null check in recursive call)
// This simplifies code - no explicit null checks here
dfs(node.left, remaining - node.val, path, result);
dfs(node.right, remaining - node.val, path, result);
// Backtrack
path.remove(path.size() - 1);
}
}
š Detailed Dry Run - Complete Backtracking
Tree:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
targetSum = 22
Complete Execution with Path Tracking:
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
BACKTRACKING TRACE - SHOWING PATH CHANGES
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
Start: path = [], result = []
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
Call: dfs(5, 22, [], [])
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
āā Add 5: path = [5]
āā Not leaf (has children)
ā
āā LEFT: dfs(4, 17, [5], []) āāāāāāāāāāāāāāāāāāāāāā
ā ā
ā āā Add 4: path = [5, 4] ā
ā āā Not leaf ā
ā ā ā
ā āā LEFT: dfs(11, 13, [5,4], []) āāāāāāāāāā ā
ā ā ā ā
ā ā āā Add 11: path = [5, 4, 11] ā ā
ā ā āā Not leaf ā ā
ā ā ā ā ā
ā ā āā LEFT: dfs(7, 2, [5,4,11], []) āā ā ā
ā ā ā ā ā ā
ā ā ā āā Add 7: path = [5,4,11,7] ā ā ā
ā ā ā āā IS LEAF! ā ā ā
ā ā ā āā Check: 2 == 7? NO ā ā ā
ā ā ā āā No children to explore ā ā ā
ā ā ā āā Remove 7: path = [5,4,11] ā ā ā
ā ā ā ā ā ā
ā ā āā RIGHT: dfs(2, 2, [5,4,11], []) ā¤ ā ā
ā ā ā ā ā ā
ā ā ā āā Add 2: path = [5,4,11,2] ā ā ā
ā ā ā āā IS LEAF! ā ā ā
ā ā ā āā Check: 2 == 2? YES! ā ā ā ā
ā ā ā āā Add copy: result = [[5,4,11,2]] ā
ā ā ā āā No children ā ā ā
ā ā ā āā Remove 2: path = [5,4,11] ā ā ā
ā ā ā ā ā ā
ā ā āā Remove 11: path = [5, 4] ā ā ā
ā ā ā ā
ā āā RIGHT: dfs(null, 13, [5,4], [...]) ā return
ā ā ā
ā āā Remove 4: path = [5] ā
ā ā
āā RIGHT: dfs(8, 17, [5], [[5,4,11,2]]) āāāāāāāāāā
ā ā
ā āā Add 8: path = [5, 8] ā
ā āā Not leaf ā
ā ā ā
ā āā LEFT: dfs(13, 9, [5,8], [...]) āāāāāāāā ā
ā ā ā ā
ā ā āā Add 13: path = [5, 8, 13] ā ā
ā ā āā IS LEAF! ā ā
ā ā āā Check: 9 == 13? NO ā ā
ā ā āā No children ā ā
ā ā āā Remove 13: path = [5, 8] ā ā
ā ā ā ā
ā āā RIGHT: dfs(4, 9, [5,8], [...]) āāāāāāāā¤ ā
ā ā ā ā
ā ā āā Add 4: path = [5, 8, 4] ā ā
ā ā āā Not leaf ā ā
ā ā ā ā ā
ā ā āā LEFT: dfs(5, 5, [5,8,4], [...]) ā ā ā
ā ā ā ā ā ā
ā ā ā āā Add 5: path = [5,8,4,5] ā ā ā
ā ā ā āā IS LEAF! ā ā ā
ā ā ā āā Check: 5 == 5? YES! ā ā ā ā
ā ā ā āā Add copy: result = ā ā ā
ā ā ā ā [[5,4,11,2], [5,8,4,5]] ā ā ā
ā ā ā āā No children ā ā ā
ā ā ā āā Remove 5: path = [5,8,4] ā ā ā
ā ā ā ā ā ā
ā ā āā RIGHT: dfs(1, 5, [5,8,4], [...]) ā ā
ā ā ā ā ā ā
ā ā ā āā Add 1: path = [5,8,4,1] ā ā ā
ā ā ā āā IS LEAF! ā ā ā
ā ā ā āā Check: 5 == 1? NO ā ā ā
ā ā ā āā No children ā ā ā
ā ā ā āā Remove 1: path = [5,8,4] ā ā ā
ā ā ā ā ā ā
ā ā āā Remove 4: path = [5, 8] ā ā
ā ā ā ā
ā āā Remove 8: path = [5] ā
ā ā
āā Remove 5: path = [] ā
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
FINAL: result = [[5,4,11,2], [5,8,4,5]]
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
Path State at Each Node:
Node 5: path = [5]
Node 4: path = [5, 4]
Node 11: path = [5, 4, 11]
Node 7: path = [5, 4, 11, 7] ā leaf, sum ā 22
path = [5, 4, 11] (backtracked)
Node 2: path = [5, 4, 11, 2] ā leaf, sum = 22! ā
path = [5, 4, 11] (backtracked)
path = [5, 4] (backtracked)
path = [5] (backtracked)
Node 8: path = [5, 8]
Node 13: path = [5, 8, 13] ā leaf, sum ā 22
path = [5, 8] (backtracked)
Node 4: path = [5, 8, 4]
Node 5: path = [5, 8, 4, 5] ā leaf, sum = 22! ā
path = [5, 8, 4] (backtracked)
Node 1: path = [5, 8, 4, 1] ā leaf, sum ā 22
path = [5, 8, 4] (backtracked)
path = [5, 8] (backtracked)
path = [5] (backtracked)
path = [] (done!)
š Complexity Analysis
Time Complexity: O(nĀ²)
Visit each node: O(n)
At each node:
- Add to path: O(1)
- Copy path (worst case): O(n)
- Remove from path: O(1)
Worst case: Skewed tree, all paths valid
O(n) nodes Ć O(n) copy = O(nĀ²)
Average case: Balanced tree
O(n) nodes Ć O(h) copy = O(n log n)
Space Complexity: O(n)
Recursion stack: O(h)
Best: O(log n)
Worst: O(n)
Current path: O(h)
Max length = height
Result storage: O(n Ć h)
Worst case: all paths stored
Total: O(n) dominated by result storage
ā ļø Common Mistakes
Mistake 1: Not Making Copy When Adding Path
// ā WRONG - Adds reference, not copy
if (node.left == null && node.right == null && remaining == node.val) {
result.add(path); // WRONG!
}
// Problem: path is modified after adding!
// All entries point to same list
// Final result: all empty or all same
// Example:
// After adding [5,4,11,2]: result = [[5,4,11,2]]
// After backtracking: path = []
// result now = [[]] ā (pointing to empty path!)
// ā CORRECT - Add copy
result.add(new ArrayList<>(path)); ā
Mistake 2: Forgetting to Backtrack
// ā WRONG - No backtracking
private void dfs(TreeNode node, int remaining,
List<Integer> path, List<List<Integer>> result) {
if (node == null) return;
path.add(node.val);
if (node.left == null && node.right == null &&
remaining == node.val) {
result.add(new ArrayList<>(path));
}
dfs(node.left, remaining - node.val, path, result);
dfs(node.right, remaining - node.val, path, result);
// Missing: path.remove(path.size() - 1);
}
// Problem: path keeps growing!
// Tree: 1
// / \
// 2 3
// After left: path = [1, 2]
// Go right: path = [1, 2, 3] ā (should be [1, 3])
// ā CORRECT - Always backtrack
path.remove(path.size() - 1); ā
Mistake 3: Not Checking Both Children are Null
// ā WRONG - Only checks remaining == node.val
if (remaining == node.val) {
result.add(new ArrayList<>(path));
}
// Problem: Adds internal nodes!
// Tree: 5
// /
// 4
// /
// 11
// Path [5, 4] has sum 9
// If target = 9, would add [5, 4] ā (not a leaf!)
// ā CORRECT - Check leaf condition
if (node.left == null && node.right == null &&
remaining == node.val) { ā
result.add(new ArrayList<>(path));
}
Mistake 4: Wrong Remaining Sum Calculation
// ā WRONG - Subtracts before checking
private void dfs(TreeNode node, int remaining, ...) {
if (node == null) return;
remaining = remaining - node.val; // WRONG placement!
path.add(node.val);
if (node.left == null && node.right == null && remaining == 0) {
result.add(new ArrayList<>(path));
}
// ...
}
// Problem: Modifies remaining before checking
// Should check: remaining == node.val
// Not: (remaining - node.val) == 0
// ā CORRECT - Check remaining == node.val
if (remaining == node.val) { ā
// OR pass remaining - node.val to children
dfs(node.left, remaining - node.val, ...);
}
Mistake 5: Modifying Path in Wrong Order
// ā WRONG - Removes before children explored
private void dfs(TreeNode node, int remaining, ...) {
if (node == null) return;
path.add(node.val);
if (/* leaf check */) {
result.add(new ArrayList<>(path));
path.remove(path.size() - 1); // WRONG! Too early!
return;
}
path.remove(path.size() - 1); // WRONG! Too early!
dfs(node.left, remaining - node.val, ...);
dfs(node.right, remaining - node.val, ...);
}
// Problem: Removes before recursing!
// Children won't have parent in path!
// ā CORRECT - Remove after all recursion
dfs(node.left, ...);
dfs(node.right, ...);
path.remove(path.size() - 1); ā After everything!
šÆ Pattern Recognition - Path Collection Problems
Core Pattern: DFS + Backtracking
Template for path collection:
private void dfs(TreeNode node, ..., List<Integer> path, ...) {
if (node == null) return;
// 1. Add current to path
path.add(node.val);
// 2. Check if condition met
if (condition) {
result.add(new ArrayList<>(path));
}
// 3. Recurse on children
dfs(node.left, ..., path, ...);
dfs(node.right, ..., path, ...);
// 4. Backtrack
path.remove(path.size() - 1);
}
Related Problems:
1. Binary Tree Paths (Problem 137)
Collect ALL root-to-leaf paths
Similar structure!
No sum checking, just collect all
2. Path Sum (Problem 135)
Check if ANY path has target sum
Similar logic, but boolean return
Don't need to collect paths
3. Path Sum III
Paths can start ANYWHERE (not just root)
More complex: need prefix sums
But still uses backtracking
4. Sum Root to Leaf Numbers
Build numbers from paths
Similar backtracking structure
Different calculation logic
When to Use This Pattern:
ā Need to collect paths
ā Explore all possibilities
ā Path depends on ancestors
ā Need to undo choices (backtrack)
ā DFS with state restoration
š Quick Revision Notes
šÆ Core Concept
Find ALL root-to-leaf paths with targetSum. Use DFS with backtracking: (1) add node to path, (2) check if leaf with correct sum, (3) recurse on children, (4) BACKTRACK by removing node. Must create copy when adding path to result (path will be modified). Check both children null for leaf (not just remaining == 0).
ā” Quick Implementation
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
pathSum(root, targetSum, new ArrayList<>(), res);
return res;
}
private void pathSum(TreeNode root, int targetSum, ArrayList<Integer> pathSum, List<List<Integer>> res) {
// reached end of the path.
if(root == null) {
return;
}
// Or else, check subtrees now.
// Add the current element
pathSum.add(root.val);
// Suppose I am at the leaf node and that node satisfies the target sum.
// Have to put this below above line after adding the root.val to the path sum list. Else, that element will not be present in the result list.
if(root.left == null && root.right == null && root.val == targetSum) {
res.add(new ArrayList<>(pathSum));
}
// Traverse LST.
pathSum(root.left, targetSum - root.val, pathSum, res);
// Traverse RST.
pathSum(root.right, targetSum - root.val, pathSum, res);
// remove the added element for next
pathSum.remove(pathSum.size() - 1);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.pathSum(TreeNode.buildTree(new Integer[] {5,4,8,11,null,13,4,7,2,null,null,5,1}), 22));
System.out.println(s.pathSum(TreeNode.buildTree(new Integer[] {1,2,3}), 5));
}
}
š Key Insights
Backtracking Necessity:
Without backtracking:
path = [5, 4, 11, 2] (after left path)
path = [5, 4, 11, 2, 8] (going right) ā
With backtracking:
path = [5, 4, 11, 2] (at leaf)
Remove 2: [5, 4, 11]
Remove 11: [5, 4]
Remove 4: [5]
path = [5, 8] (going right) ā
Backtracking restores state! š
Copy vs Reference:
WRONG:
result.add(path); // Adds reference!
After: result = [[5,4,11,2]]
Path modified: path = []
Result now: [[]] ā (all entries point to same list!)
CORRECT:
result.add(new ArrayList<>(path)); // Copy!
Snapshot of current state
Independent of future changes ā
Always copy when storing mutable objects! šÆ
Leaf Check is Critical:
WRONG:
if (remaining == node.val) {
result.add(path);
}
Adds internal nodes! ā
CORRECT:
if (node.left == null && node.right == null &&
remaining == node.val) {
result.add(path);
}
Only adds complete root-to-leaf paths! ā
Must check BOTH children null! š
Backtracking Order:
Order matters:
1. Add to path
2. Check condition / recurse
3. Remove from path
Not:
1. Add to path
2. Remove from path ā (too early!)
3. Recurse ā (children won't see current!)
Remove AFTER all recursion completes! ā”
šŖ Memory Aid
"Add, recurse, remove (backtrack)!"
"Copy when storing (new ArrayList)!"
"Leaf = both children null!"
"Backtrack restores state!" āØ
ā ļø Don't Forget
- Add copy to result (new ArrayList!)
- Backtrack after recursion (remove last!)
- Check leaf properly (both children null!)
- Pass remaining - node.val (to children!)
- Remove in correct order (after all recursion!)
- Path modified by reference (same list throughout!)
š Congratulations!
You've mastered backtracking on trees!
What You Learned:
ā
Backtracking pattern - Add/recurse/remove
ā
Path collection - Copying vs reference
ā
State restoration - Undoing choices
ā
Leaf checking - Both children null
ā
DFS with state - Passing mutable path
ā
Multiple solutions - Collecting all paths
The Backtracking Pattern:
Classic backtracking structure:
1. Make choice (add to path)
2. Explore (recurse on children)
3. Undo choice (remove from path)
Universal pattern for:
- Path problems
- Combination problems
- Permutation problems
- Constraint satisfaction
Fundamental algorithm pattern! šÆ
Interview Mastery:
Interviewer: "Find all root-to-leaf paths with sum"
Your response:
"Use DFS with backtracking.
Key steps:
1. Add current node to path
2. Check if leaf with target sum
3. Recurse on both children
4. Backtrack: remove current node
Critical: Copy path when adding to result
(path will be modified later)
Time: O(nĀ²) worst case, Space: O(n)"
Shows algorithm mastery! šÆ
You've learned a fundamental pattern used across many problems! šāØšÆ