Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given a binary tree, return all root-to-leaf paths.
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
Approach 1: DFS with Backtracking
Algorithm
- Use DFS to traverse the tree
- Keep track of current path
- When reaching a leaf node, add the path to result
- Backtrack by removing the last element when returning
Solution
Python:
def binaryTreePaths(root):
"""
DFS with backtracking approach
Time: O(n) - visit each node once
Space: O(h) - recursion stack and path storage
"""
if not root:
return []
result = []
def dfs(node, path):
# Add current node to path
path.append(str(node.val))
# If leaf node, add path to result
if not node.left and not node.right:
result.append("->".join(path))
else:
# Continue DFS on children
if node.left:
dfs(node.left, path)
if node.right:
dfs(node.right, path)
# Backtrack: remove current node from path
path.pop()
dfs(root, [])
return result
Java:
class Solution {
/**
* DFS with backtracking approach
* Time: O(n) - visit each node once
* Space: O(h) - recursion stack and path storage
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if (root == null) return result;
dfs(root, new ArrayList<>(), result);
return result;
}
private void dfs(TreeNode node, List<String> path, List<String> result) {
// Add current node to path
path.add(String.valueOf(node.val));
// If leaf node, add path to result
if (node.left == null && node.right == null) {
result.add(String.join("->", path));
} else {
// Continue DFS on children
if (node.left != null) {
dfs(node.left, path, result);
}
if (node.right != null) {
dfs(node.right, path, result);
}
}
// Backtrack: remove current node from path
path.remove(path.size() - 1);
}
}
Go:
// binaryTreePaths - DFS with backtracking approach
// Time: O(n) - visit each node once
// Space: O(h) - recursion stack and path storage
func binaryTreePaths(root *TreeNode) []string {
if root == nil {
return []string{}
}
var result []string
var dfs func(*TreeNode, []string)
dfs = func(node *TreeNode, path []string) {
// Add current node to path
path = append(path, strconv.Itoa(node.Val))
// If leaf node, add path to result
if node.Left == nil && node.Right == nil {
result = append(result, strings.Join(path, "->"))
} else {
// Continue DFS on children
if node.Left != nil {
dfs(node.Left, path)
}
if node.Right != nil {
dfs(node.Right, path)
}
}
// Backtrack: remove current node from path
path = path[:len(path)-1]
}
dfs(root, []string{})
return result
}
JavaScript:
/**
* DFS with backtracking approach
* Time: O(n) - visit each node once
* Space: O(h) - recursion stack and path storage
*/
function binaryTreePaths(root) {
if (!root) return [];
const result = [];
function dfs(node, path) {
// Add current node to path
path.push(node.val.toString());
// If leaf node, add path to result
if (!node.left && !node.right) {
result.push(path.join("->"));
} else {
// Continue DFS on children
if (node.left) {
dfs(node.left, path);
}
if (node.right) {
dfs(node.right, path);
}
}
// Backtrack: remove current node from path
path.pop();
}
dfs(root, []);
return result;
}
C#:
public class Solution {
/// <summary>
/// DFS with backtracking approach
/// Time: O(n) - visit each node once
/// Space: O(h) - recursion stack and path storage
/// </summary>
public IList<string> BinaryTreePaths(TreeNode root) {
var result = new List<string>();
if (root == null) return result;
Dfs(root, new List<string>(), result);
return result;
}
private void Dfs(TreeNode node, List<string> path, List<string> result) {
// Add current node to path
path.Add(node.val.ToString());
// If leaf node, add path to result
if (node.left == null && node.right == null) {
result.Add(string.Join("->", path));
} else {
// Continue DFS on children
if (node.left != null) {
Dfs(node.left, path, result);
}
if (node.right != null) {
Dfs(node.right, path, result);
}
}
// Backtrack: remove current node from path
path.RemoveAt(path.Count - 1);
}
}
Key Insights
Backtracking Pattern: This problem demonstrates the classic backtracking pattern where we explore all paths and backtrack when we reach a dead end.
Path Management: We need to maintain the current path as we traverse the tree, adding nodes when going down and removing them when backtracking.
Leaf Detection: A leaf node is identified when both left and right children are null.
String Joining: The “->” separator is used to format the output as required.
Edge Cases
- Single Node Tree: Tree with only root node
- Linear Tree: Tree that looks like a linked list
- Complete Binary Tree: Tree with all levels filled
- Empty Tree: Null root (handled by early return)
Follow-up Questions
- Print paths with sum equal to target: Modify to only print paths where sum equals a given target
- Find longest path: Return the longest root-to-leaf path
- Path with maximum sum: Find the path with maximum sum from root to leaf
- Serialize paths: Convert paths to a different format (e.g., array of arrays)
Common Mistakes
- Forgetting to backtrack: Not removing the current node from path when returning
- String conversion: Forgetting to convert node values to strings
- Path copying: In iterative approach, not creating new path arrays for each child
- Null checks: Not handling null children properly