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
Use an iterative depth-first search approach with a stack to track nodes and their corresponding paths. Use StringBuilder for efficient string manipulation.
Algorithm
- Initialize empty result list and stacks for nodes and paths
- Push root node and its value to respective stacks
- While node stack is not empty:
- Pop current node and path
- If leaf node, add path to result
- Push right and left children with their paths to stacks
Walkthrough
This approach uses a stack to perform iterative DFS traversal. We maintain two stacks: one for nodes and another for the corresponding paths. We use StringBuilder for efficient path building.
class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> paths = new ArrayList<>(); if (root == null) return paths; Stack<TreeNode> nodeStack = new Stack<>(); Stack<StringBuilder> pathStack = new Stack<>(); nodeStack.push(root); pathStack.push(new StringBuilder(Integer.toString(root.val))); while (!nodeStack.isEmpty()) { TreeNode node = nodeStack.pop(); StringBuilder path = pathStack.pop(); if (node.left == null && node.right == null) { paths.add(path.toString()); continue; } if (node.right != null) { nodeStack.push(node.right); StringBuilder rightPath = new StringBuilder(path); rightPath.append("->").append(node.right.val); pathStack.push(rightPath); } if (node.left != null) { nodeStack.push(node.left); StringBuilder leftPath = new StringBuilder(path); leftPath.append("->").append(node.left.val); pathStack.push(leftPath); } } return 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 and stack space
Trade-offs
Pros
More efficient string manipulation using StringBuilder
No recursion stack overhead
Better memory management
Cons
More complex implementation than recursive approach
Requires additional data structures (stacks)
Need to manage two parallel stacks
Use recursive DFS with StringBuilder for path building and implement backtracking to reuse the same StringBuilder object, minimizing object creation.
Algorithm
- Initialize empty result list
- Create single StringBuilder for path building
- In DFS helper:
- Append current node value to path
- If leaf node, add path to result
- Recursively process children
- Backtrack by removing current node from path
Walkthrough
This approach combines the benefits of recursion with efficient string manipulation using StringBuilder and backtracking. We maintain a single StringBuilder object throughout the traversal.
class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> paths = new ArrayList<>(); if (root == null) return paths; dfs(root, new StringBuilder(), paths); return paths; } private void dfs(TreeNode node, StringBuilder path, List<String> paths) { int len = path.length(); if (len > 0) { path.append("->"); } path.append(node.val); if (node.left == null && node.right == null) { paths.add(path.toString()); } else { if (node.left != null) { dfs(node.left, path, paths); } if (node.right != null) { dfs(node.right, path, paths); } } // Backtrack: remove the current node and arrow from path path.setLength(len); }}Complexity
Time
O(N) where N is the number of nodes in the tree. Each node is visited exactly once.
Space
O(H) where H is the height of the tree for recursion stack, plus O(N) for storing the final paths
Trade-offs
Pros
Most efficient string manipulation
Minimizes object creation
Optimal memory usage through backtracking
Combines benefits of recursion and StringBuilder
Cons
Requires careful management of StringBuilder length
Need to handle backtracking correctly
Slightly more complex logic than basic recursive approach
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 ); } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < string > binaryTreePaths ( TreeNode * root ) { vector < string > ans ; vector < string > t ; function < void ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) { return ; } t . push_back ( to_string ( root -> val )); if ( ! root -> left && ! root -> right ) { ans . push_back ( join ( t )); } else { dfs ( root -> left ); dfs ( root -> right ); } t . pop_back (); }; dfs ( root ); return ans ; } string join ( vector < string >& t , string sep = "->" ) { string ans ; for ( int i = 0 ; i < t . size (); ++ i ) { if ( i > 0 ) { ans += sep ; } ans += t [ i ]; } return ans ; } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def binaryTreePaths ( self , root : Optional [ TreeNode ]) -> List [ str ]: def dfs ( root : Optional [ TreeNode ]): if root is None : return t . append ( str ( root . val )) if root . left is None and root . right is None : ans . append ( "->" . join ( t )) else : dfs ( root . left ) dfs ( root . right ) t . pop () ans = [] t = [] dfs ( root ) return ansVideo 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.