Binary Tree Paths
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
Use recursive depth-first search (DFS) to traverse the binary tree and build paths as strings during traversal. At each node, append the current node's value to the path and use string concatenation.
Algorithm
- Initialize an empty list to store all paths
- If root is null, return empty list
- Call DFS helper function with initial empty path
- In DFS helper:
- Append current node value to path
- If current node is leaf, add path to result list
- Recursively call DFS on left and right children if they exist
Walkthrough
This approach uses recursive DFS to traverse the binary tree from root to leaf. At each node, we append the current node's value to the current path string. When we reach a leaf node (node with no children), we add the complete path to our result list.
class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> paths = new ArrayList<>(); if (root == null) return paths; dfs(root, "", paths); return paths; } private void dfs(TreeNode node, String path, List<String> paths) { // Build current path path += (path.isEmpty() ? "" : "->") + node.val; // If leaf node, add path to result if (node.left == null && node.right == null) { paths.add(path); return; } // Recurse on children if (node.left != null) dfs(node.left, path, paths); if (node.right != null) dfs(node.right, path, paths); }}Complexity
Time
O(N) where N is the number of nodes in the tree. Each node is visited exactly once.
Space
O(N) for storing the paths. In worst case (skewed tree), the recursion stack can go up to O(N)
Trade-offs
Pros
Simple and intuitive implementation
Easy to understand and maintain
Works directly with string representation
Cons
Creates new string objects at each recursive call
String concatenation is inefficient
Higher memory usage due to string immutability
Solutions
Solution
/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { private List < String > ans = new ArrayList <>(); private List < String > t = new ArrayList <>(); public List < String > binaryTreePaths ( TreeNode root ) { dfs ( root ); return ans ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } t . add ( root . val + "" ); if ( root . left == null && root . right == null ) { ans . add ( String . join ( "->" , t )); } else { dfs ( root . left ); dfs ( root . right ); } t . remove ( t . size () - 1 ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.