137. Binary Tree Paths
š LeetCode Problem: 257. Binary Tree Paths
š Difficulty: Easy
š·ļø Topics: Binary Trees, Recursion, DFS, Backtracking, Path Construction
Problem Statement
Given the root of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.
Example 1:
Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]
Example 2:
Input: root = [1]
Output: ["1"]
Constraints:
- The number of nodes in the tree is in the range [1, 100]
- -100 <= Node.val <= 100
š³ Visual Understanding - Drawing All Paths!
Example 1: Multiple Paths
Tree: [1,2,3,null,5]
1 ā Start here
/ \
2 3 ā Two branches
\
5 ā One leaf here, one leaf at 3
All root-to-leaf paths:
Path 1: 1 ā 2 ā 5 = "1->2->5" ā
Path 2: 1 ā 3 = "1->3" ā
Visual representation:
1
/ \
2 3 Path to 3: [1,3]
\
5 Path to 5: [1,2,5]
Total: 2 paths
Output: ["1->2->5", "1->3"]
Example 2: Single Node
Tree: [1]
1 ā This is both root AND leaf!
Only one path:
Path 1: 1 = "1" ā
Output: ["1"]
Understanding "Root-to-Leaf":
MUST reach a leaf (both children null)!
Valid paths:
1
/ \
2 3 ā 2 and 3 are leaves ā
Paths: "1->2", "1->3"
Invalid "paths":
1 ā Can't stop here!
/ \
2 3
/
4 ā Must continue to leaf (4)
Only valid path: "1->2->4"
Can't return "1" or "1->2" (not complete paths)
More Examples:
Example 3: Complete binary tree
1
/ \
2 3
/ \ / \
4 5 6 7
All leaves: 4, 5, 6, 7
Paths:
"1->2->4"
"1->2->5"
"1->3->6"
"1->3->7"
Example 4: Left-skewed tree
1
/
2
/
3
Only one path:
"1->2->3"
Example 5: All leaves at different levels
1
/ \
2 3
/ \
4 5
/
6
Paths:
"1->2->4->6" (depth 4)
"1->3->5" (depth 3)
š§ The AHA Moment - Backtracking Pattern!
The Key Question:
"How do I collect ALL paths from root to leaves?"
Recursive + Backtracking Insight:
This problem requires BACKTRACKING!
Why?
We need to:
1. Build a path as we go down
2. When we hit a leaf, save the path
3. BACKTRACK to try other branches
Example:
1
/ \
2 3
Process:
1. Start at 1, path = "1"
2. Go to 2, path = "1->2"
3. Hit leaf 2, save "1->2" ā
4. BACKTRACK to 1, path = "1"
5. Go to 3, path = "1->3"
6. Hit leaf 3, save "1->3" ā
7. Done!
Without backtracking, we'd lose track of where we are!
Visual Backtracking:
Tree:
1
/ \
2 3
\
5
DFS Traversal with path building:
Start: path = ""
Visit 1: path = "1"
ā
āā Visit 2: path = "1->2"
ā ā
ā āā Try left: null, skip
ā ā
ā āā Visit 5: path = "1->2->5"
ā ā
ā āā Leaf! Save "1->2->5" ā
ā ā
ā āā BACKTRACK to 2: path = "1->2"
ā
āā BACKTRACK to 1: path = "1"
ā
āā Visit 3: path = "1->3"
ā
āā Leaf! Save "1->3" ā
ā
āā BACKTRACK to 1: path = "1"
Result: ["1->2->5", "1->3"]
š§ Recursive Thinking - Building the Solution
Approach 1: Build String Path
We build the path as a String as we recurse
At each node:
- Add current node to path
- If leaf: add path to result
- If not leaf: recurse with updated path
The path STRING is passed down
No need to explicitly backtrack (string is immutable in Java)
Base Case:
Base Case: Node is a leaf
Add complete path to result list
Check:
if (node.left == null && node.right == null) {
result.add(currentPath);
return;
}
This is where we collect the path!
Recursive Case:
For non-leaf nodes:
1. Add current node to path
2. Recurse on left child (if exists)
3. Recurse on right child (if exists)
Example:
currentPath = "1->2"
If left child exists:
recurse with "1->2->5"
If right child exists:
recurse with "1->2->7"
šÆ Solution 1: Recursive DFS with String Building
Implementation:
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
// Handle null root
if (root == null) {
return result;
}
// Start DFS with root value
dfs(root, String.valueOf(root.val), result);
return result;
}
private void dfs(TreeNode node, String path, List<String> result) {
// Base Case: Leaf node - add complete path
// WHY? Path must end at a leaf!
if (node.left == null && node.right == null) {
result.add(path);
return;
}
// Recursive Case: Continue building path
// Go left if possible
if (node.left != null) {
dfs(node.left, path + "->" + node.left.val, result);
}
// Go right if possible
if (node.right != null) {
dfs(node.right, path + "->" + node.right.val, result);
}
// Note: No explicit backtracking needed!
// WHY? Strings are immutable - each recursive call
// has its own copy of the path string
}
}
Cleaner Version:
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root == null) return paths;
buildPaths(root, "", paths);
return paths;
}
private void buildPaths(TreeNode node, String path, List<String> paths) {
// Build current path
path += node.val;
// If leaf, save path
if (node.left == null && node.right == null) {
paths.add(path);
return;
}
// Continue with "->" separator
path += "->";
// Recurse on children
if (node.left != null) {
buildPaths(node.left, path, paths);
}
if (node.right != null) {
buildPaths(node.right, path, paths);
}
}
}
šÆ Solution 2: Recursive DFS with List Building (Explicit Backtracking)
Implementation:
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if (root == null) return result;
List<Integer> path = new ArrayList<>();
dfs(root, path, result);
return result;
}
private void dfs(TreeNode node, List<Integer> path, List<String> result) {
// Add current node to path
path.add(node.val);
// If leaf, convert path to string and save
if (node.left == null && node.right == null) {
result.add(pathToString(path));
} else {
// Continue exploring
if (node.left != null) {
dfs(node.left, path, result);
}
if (node.right != null) {
dfs(node.right, path, result);
}
}
// BACKTRACK: Remove current node
// WHY? So parent can try other branches with clean path
path.remove(path.size() - 1);
}
private String pathToString(List<Integer> path) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < path.size(); i++) {
sb.append(path.get(i));
if (i < path.size() - 1) {
sb.append("->");
}
}
return sb.toString();
}
}
Why Explicit Backtracking?
With List (mutable):
path.add(5); // Modifies the list
dfs(left, path); // Passes modified list
path.remove(...); // Must restore! (backtrack)
Without backtracking:
path = [1, 2, 5]
After left recursion: still [1, 2, 5]
Try right: adds to [1, 2, 5] ā WRONG!
With backtracking:
path = [1, 2, 5]
After left recursion + backtrack: [1, 2]
Try right: adds to [1, 2] ā CORRECT!
With String (immutable):
path = "1->2";
dfs(left, path + "->5"); // Creates NEW string
// Original path still "1->2" - no need to backtrack!
š Detailed Dry Run with Recursion Visualization
Tree:
1
/ \
2 3
\
5
Complete Recursion Flow (String Approach):
CALL STACK VISUALIZATION:
Level 0: binaryTreePaths(1)
ā
āā result = []
āā Start: dfs(1, "1", result)
ā
ā Level 1: dfs(1, "1", result)
ā ā
ā āā node = 1, not a leaf (has children)
ā āā path = "1"
ā ā
ā āā LEFT exists (2), recurse āāāāāāāāāāāāāā
ā ā ā
ā ā Level 2: dfs(2, "1->2", result) ā
ā ā ā ā
ā ā āā node = 2, not a leaf (has right) ā
ā ā āā path = "1->2" ā
ā ā ā ā
ā ā āā LEFT is null, skip ā
ā ā ā ā
ā ā āā RIGHT exists (5), recurse āāāāāāāāā
ā ā ā ā
ā ā ā Level 3: dfs(5, "1->2->5", result)ā
ā ā ā ā ā
ā ā ā āā node = 5, IS A LEAF! ā ā
ā ā ā āā path = "1->2->5" ā
ā ā ā āā Add to result: ["1->2->5"] ā
ā ā ā āā return ā
ā ā ā ā
ā ā āā [Returned from 5] ā
ā ā No more children ā
ā ā ā
ā āā [Returned from 2] ā
ā ā
ā āā RIGHT exists (3), recurse āāāāāāāāāāāāā
ā ā ā
ā ā Level 2: dfs(3, "1->3", result) ā
ā ā ā ā
ā ā āā node = 3, IS A LEAF! ā ā
ā ā āā path = "1->3" ā
ā ā āā Add to result: ["1->2->5","1->3"] ā
ā ā āā return ā
ā ā ā
ā āā [Returned from 3] ā
ā ā
ā āā All children processed ā
ā ā
āā return result: ["1->2->5", "1->3"] ā
FINAL RESULT: ["1->2->5", "1->3"]
Path Building Visualization:
Step-by-step path construction:
Step 1: Visit node 1
path = "1"
Not a leaf ā continue
Step 2: Visit node 2 (left child of 1)
path = "1" + "->" + "2" = "1->2"
Not a leaf ā continue
Step 3: Visit node 5 (right child of 2)
path = "1->2" + "->" + "5" = "1->2->5"
Is a leaf! ā Save "1->2->5" ā
Step 4: Back to node 1 (string immutable, so still "1")
Step 5: Visit node 3 (right child of 1)
path = "1" + "->" + "3" = "1->3"
Is a leaf! ā Save "1->3" ā
Result: ["1->2->5", "1->3"]
š Dry Run - List Approach with Backtracking
Tree:
1
/ \
2 3
With Explicit Backtracking:
Call Stack:
Level 0: dfs(1, [], result)
ā
āā path.add(1) ā path = [1]
āā Not a leaf
ā
āā LEFT exists, recurse āāāāāāāāāāāāāāāāāāā
ā ā
ā Level 1: dfs(2, [1], result) ā
ā ā ā
ā āā path.add(2) ā path = [1, 2] ā
ā āā IS A LEAF! ā ā
ā āā Convert to string: "1->2" ā
ā āā result = ["1->2"] ā
ā āā BACKTRACK: path.remove(2) ā
ā ā path = [1] ā
ā āā return ā
ā ā
āā path = [1] (after backtrack!) ā
ā ā
āā RIGHT exists, recurse āāāāāāāāāāāāāāāāāā
ā ā
ā Level 1: dfs(3, [1], result) ā
ā ā ā
ā āā path.add(3) ā path = [1, 3] ā
ā āā IS A LEAF! ā ā
ā āā Convert to string: "1->3" ā
ā āā result = ["1->2", "1->3"] ā
ā āā BACKTRACK: path.remove(3) ā
ā ā path = [1] ā
ā āā return ā
ā ā
āā BACKTRACK: path.remove(1) ā
ā path = [] ā
ā ā
āā return result: ["1->2", "1->3"] ā
Note: Backtracking ensures clean path for each branch!
š Complexity Analysis
Time Complexity: O(n)
Where n = number of nodes
Why?
- Visit each node exactly once
- At each node: O(1) operations (append to string)
But wait! String concatenation?
- Each concatenation creates new string
- For path of length k: O(k) per concatenation
Amortized analysis:
- Total characters across all paths = O(n)
- Average path length = O(log n) to O(n)
Overall: O(n) visits Ć O(k) string ops
Best case: O(n log n) - balanced tree
Worst case: O(nĀ²) - skewed tree
For interviews: Say O(n) or O(n Ć height)
Space Complexity: O(n)
Space used:
1. Recursion stack: O(h) where h = height
2. Result list: O(n) - stores all paths
3. Path strings: O(n) total characters
Best case (balanced): O(log n) + O(n) = O(n)
Worst case (skewed): O(n) + O(n) = O(n)
Overall: O(n)
Note: Result list dominates space complexity
ā ļø Common Mistakes
Mistake 1: Not Checking for Leaf
// ā WRONG - Adds incomplete paths!
private void dfs(TreeNode node, String path, List<String> result) {
if (node == null) return;
path += node.val;
result.add(path); // Adds EVERY node, not just leaves!
// ...
}
// Tree: 1
// / \
// 2 3
// Would add: "1", "1->2", "1->3"
// Should only add: "1->2", "1->3" (leaves!)
// ā CORRECT - Check for leaf
if (node.left == null && node.right == null) {
result.add(path); // Only add at leaves!
}
Mistake 2: Forgetting to Backtrack (List Approach)
// ā WRONG - No backtracking!
private void dfs(TreeNode node, List<Integer> path, List<String> result) {
path.add(node.val);
if (node.left == null && node.right == null) {
result.add(pathToString(path));
}
if (node.left != null) dfs(node.left, path, result);
if (node.right != null) dfs(node.right, path, result);
// Missing: path.remove(path.size() - 1);
}
// Result: Paths accumulate incorrectly!
// ā CORRECT - Backtrack after exploring
path.remove(path.size() - 1); // Clean up!
Mistake 3: Building String Incorrectly
// ā WRONG - Missing arrow between nodes
path = path + node.val; // "123" instead of "1->2->3"
// ā WRONG - Extra arrow at start
path = "->" + node.val + path; // "->1->2->3"
// ā WRONG - Extra arrow at end
if (node.left == null && node.right == null) {
result.add(path + "->"); // "1->2->3->"
}
// ā CORRECT - Arrow between nodes only
path = path + "->" + node.val;
// Or handle first node specially
Mistake 4: Modifying String Wrong
// ā WRONG - Trying to backtrack string
String path = "1->2";
path += "->5";
// How to remove "->5"? Can't easily!
path = path.substring(0, path.length() - 3); // Messy!
// ā BETTER - Use String (immutable, no backtrack needed)
dfs(node.left, path + "->" + node.left.val, result);
// ā OR - Use StringBuilder with explicit backtracking
StringBuilder path = new StringBuilder();
path.append("->").append(node.val);
// ... explore ...
path.setLength(path.length() - 3); // Backtrack
Mistake 5: Starting with Wrong Path
// ā WRONG - Starts with arrow
dfs(root, "", result); // First call with empty string
// In dfs: path += "->" + node.val;
// Result: "->1->2->3"
// ā CORRECT - Start with root value
dfs(root, String.valueOf(root.val), result);
// Then add arrows for children
Mistake 6: Not Handling Single Node
// ā WRONG - Doesn't handle single node tree
if (root == null) return result;
dfs(root, "", result);
// Tree: [1]
// If leaf check comes after building path,
// might return empty or malformed
// ā CORRECT - Handle single node properly
if (root == null) return result;
dfs(root, String.valueOf(root.val), result);
// Leaf check works: "1" added correctly
šÆ Pattern Recognition - Path Collection
Core Pattern: Collect All Paths
Template for collecting all root-to-leaf paths:
void collectPaths(TreeNode node,
PathType currentPath,
List<PathType> result) {
// Add current node to path
updatePath(currentPath, node);
// Base case: Leaf - save path
if (isLeaf(node)) {
result.add(copyOf(currentPath));
return;
}
// Recursive case: Continue exploring
if (node.left != null) {
collectPaths(node.left, currentPath, result);
}
if (node.right != null) {
collectPaths(node.right, currentPath, result);
}
// Backtrack if using mutable data structure
if (isMutable) {
backtrack(currentPath);
}
}
Related Problems:
1. Path Sum II (Problem 135 variation)
Collect all paths that sum to target
- Same pattern!
- Additional condition: sum equals target
- Still collect at leaves
2. Sum Root to Leaf Numbers
Each path forms a number, sum all numbers
- Similar path building
- But convert to number instead of string
- Return sum, not list
3. Binary Tree Maximum Path Sum
Find maximum sum path (can start/end anywhere)
- More complex: not root-to-leaf
- Uses depth calculation
- Different pattern
4. All Paths From Source to Target (Graph)
Same concept but for graphs
- DFS with backtracking
- Collect all paths from source to target
- Very similar structure!
When to Use This Pattern:
ā "Find all paths" problems
ā "Collect paths that satisfy X" problems
ā Root-to-leaf enumeration
ā When you need ALL solutions (not just one)
ā Backtracking + DFS combination
š Quick Revision Notes
šÆ Core Concept
Find all root-to-leaf paths as strings. Use DFS + backtracking. Build path as you recurse down. At leaf, save complete path. Two approaches: (1) String (immutable, no explicit backtrack), (2) List (mutable, must backtrack). Format: "node1->node2->node3". Must reach leaf (both children null) to add path.
ā” Quick Implementation
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
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<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if(root == null) {
return res;
}
// // Approach 1 - More natural using lists.
// Create 1 list per 1 root-to-leaf path.
// usingList(root, new ArrayList<>(), res);
// Approach 2 - using strings.
usingString(root, String.valueOf(root.val), res);
return res;
}
private void usingString(TreeNode root, String currPath, List<String> res) {
// same base case as earlier.
if(root.left == null && root.right == null) {
res.add(currPath);
return;
}
// Same as earlier. Instead of adding list, directly modifying list.
// Considering only when left part is there.
if(root.left != null) {
usingString(root.left, currPath + "->" + root.left.val, res);
}
// Considering only when right part is there.
if(root.right != null) {
usingString(root.right, currPath + "->" + root.right.val, res);
}
}
private void usingList(TreeNode root, ArrayList<Integer> currPath, List<String> res) {
// base case - reached leaf node. Add the leaf node to the path and build the result.
// currPath holds root-to-leaf paths.
if(root.left == null && root.right == null) {
currPath.add(root.val);
buildPath(currPath, res);
return;
}
// Add the incoming node. For example, 1
currPath.add(root.val);
// Considering only when left part is there.
if(root.left != null) {
usingList(root.left, new ArrayList<>(currPath), res);
}
// Considering only when right part is there.
if(root.right != null) {
usingList(root.right, new ArrayList<>(currPath), res);
}
// Remove the node before tracking back to the previous call.
// Recusion concept: whatever got added should be removed before going back.
currPath.remove(currPath.size() - 1);
}
private void buildPath(ArrayList<Integer> path, List<String> res) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < path.size(); i++) {
sb.append(path.get(i));
if(i != path.size() - 1) {
sb.append("->");
}
}
res.add(sb.toString());
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.binaryTreePaths(TreeNode.buildTree(new Integer[] {1,2,3,null,5}))); //[1->2->5, 1->3]
}
}
š Key Insights
String vs List Approach:
String (immutable):
+ No explicit backtracking needed
+ Simpler code
- New string created each time
List (mutable):
+ More efficient (no string copying)
+ Good for large trees
- Must explicitly backtrack
- More code
For interviews: Use String (simpler!)
Why Backtracking Matters:
Tree:
1
/ \
2 3
Without backtracking (List):
path = [1, 2]
After left: path = [1, 2]
Try right: path becomes [1, 2, 3] ā WRONG!
With backtracking:
path = [1, 2]
After left + backtrack: path = [1]
Try right: path becomes [1, 3] ā CORRECT!
Backtracking restores state for next branch!
Leaf Requirement:
Same as Path Sum and Min Depth!
Only add path at LEAF:
if (node.left == null && node.right == null)
Can't add at every node:
Would include incomplete paths!
šŖ Memory Aid
"Build path down, save at leaf!"
"String: no backtrack needed!"
"List: backtrack or wrong path!"
"Arrow between nodes: ->!" āØ
ā ļø Don't Forget
- Check for leaf (both children null)
- Start with root value (not empty string)
- Add arrows between nodes (not at start/end)
- String approach simpler (no backtracking!)
- List approach must backtrack (restore state!)
- Convert list to string only at leaves
š Backtracking Pattern
// Generic backtracking template
void backtrack(node, currentState, result) {
// Add current to state
state.add(node);
// Success condition?
if (isSuccess(state)) {
result.add(copy(state));
} else {
// Continue exploring
for (child : node.children) {
backtrack(child, state, result);
}
}
// BACKTRACK: restore state
state.remove(node);
}
For this problem:
state = path (string or list)
success = leaf node
children = left and right
š Congratulations!
You've mastered path collection with backtracking!
What You Learned:
ā
Path collection - Finding all root-to-leaf paths
ā
Backtracking concept - Build path, save, restore
ā
String vs List - Immutable vs mutable approaches
ā
Leaf requirement - Same pattern from previous problems
ā
Path formatting - Building "1->2->3" format
ā
DFS traversal - With state management
Pattern Evolution:
Problem 135: Path Sum
- Find IF path exists with sum
- Return: boolean
- Stop when found
Problem 137: Binary Tree Paths
- Find ALL paths
- Return: List<String>
- Collect all, no early stop
Key difference:
135: Existence check (boolean)
137: Collection (list)
Both require reaching LEAF! ā
The Backtracking Skill:
You now understand:
ā When to backtrack (mutable state)
ā When not needed (immutable state)
ā How to restore state
ā Why it's necessary
This applies to:
- Path problems
- Permutations
- Combinations
- Subsets
- N-Queens
- Sudoku solver
Fundamental algorithm skill! š
Next Steps:
Perfect problems to reinforce this: - Path Sum II (exact same pattern!) - Sum Root to Leaf Numbers (similar building) - All Paths Source to Target (graphs!)
You're building powerful problem-solving patterns! š³šÆāØ