Problem Statement
Given the root of a binary tree, print all root-to-leaf paths.
A path starts at the root and ends at a leaf node.
Brute Force Intuition
In an interview, you can explain it like this:
Traverse the tree while maintaining the current path. Whenever a leaf node is reached, store the path.
Since every node belongs to exactly one traversal path, DFS naturally fits.
Complexity
- Time Complexity: O(N)
- Space Complexity: O(H)
Moving Towards the Optimal Approach
Observe that a path changes while moving down the tree.
Whenever recursion returns,
the last node should be removed.
This is exactly:
Backtracking
Pattern Recognition
Whenever you see:
- Root to Leaf
- Generate All Paths
- Explore Every Possibility
Think:
DFS + Backtracking
Key Observation
Maintain:
Current Path
Whenever:
Leaf Node
is reached,
store a copy of the path.
After exploring,
remove the current node.
Optimal Approach
Step 1
Add current node.
Step 2
If leaf:
Store Path
Step 3
Explore:
Left
↓
Right
Step 4
Backtrack.
path.remove(path.size()-1);
Optimal Java Solution
class Solution {
public static ArrayList<ArrayList<Integer>>
Paths(Node root) {
ArrayList<ArrayList<Integer>> ans =
new ArrayList<>();
dfs(root,
new ArrayList<>(),
ans);
return ans;
}
static void dfs(Node root,
ArrayList<Integer> path,
ArrayList<ArrayList<Integer>> ans) {
if (root == null)
return;
path.add(root.data);
if (root.left == null &&
root.right == null) {
ans.add(new ArrayList<>(path));
} else {
dfs(root.left, path, ans);
dfs(root.right, path, ans);
}
path.remove(path.size() - 1);
}
}
Dry Run
1
/ \
2 3
/
4
Current Path:
1
↓
1 2
↓
1 2 4
Leaf:
Store:
[1,2,4]
Backtrack:
1 2
↓
1
↓
Explore:
3
Store:
[1,3]
Final Answer:
[[1,2,4],[1,3]]
Why Backtracking Works?
Every recursive call adds one node to the path.
Once that subtree is completely explored,
the node is removed,
allowing the same path list to be reused for other branches.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(H) |
Interview One-Liner
Use DFS with backtracking by maintaining the current path, storing it at every leaf node, and removing the node while returning from recursion.
Pattern Learned
DFS
↓
Current Path
↓
Leaf
↓
Store Copy
↓
Backtrack
Similar Problems
- Root to Leaf Paths
- Path Sum II
- Binary Tree Paths
- Subsets
- Combination Sum
Memory Trick
Think:
Visit Node
↓
Add To Path
↓
Leaf?
↓
Store Copy
↓
Remove Node
Mental Model
DFS
↓
Path
↓
Leaf
↓
Answer
↓
Backtrack
Whenever you hear:
"Print all root-to-leaf paths"
your brain should immediately think:
DFS + Backtracking
SOCIAL SHARE CARD GENERATOR