# Binary Tree Paths
**Difficulty:** EASY
[External](https://leetcode.com/problems/binary-tree-paths)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-paths
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** String, Tree, Binary Tree
**Companies:** [Google](https://scaleengineer.com/companies/google), [Capital One](https://scaleengineer.com/companies/capital-one), [Revolut](https://scaleengineer.com/companies/revolut)
---
## Problem
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:**

![](https://assets.glich.co/dsa/binary-tree-paths/image0.jpg) 

**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
## Recursive DFS with String Building
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.
**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)
**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
### Explanation
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.

```java
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);
    }
}
```
### Algorithm
1. Initialize an empty list to store all paths
2. If root is null, return empty list
3. Call DFS helper function with initial empty path
4. 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

## Iterative DFS with StringBuilder
Use an iterative depth-first search approach with a stack to track nodes and their corresponding paths. Use StringBuilder for efficient string manipulation.
**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
**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
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Initialize empty result list and stacks for nodes and paths
2. Push root node and its value to respective stacks
3. 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

## Recursive DFS with StringBuilder and Backtracking
Use recursive DFS with StringBuilder for path building and implement backtracking to reuse the same StringBuilder object, minimizing object creation.
**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
**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
### Explanation
This approach combines the benefits of recursion with efficient string manipulation using StringBuilder and backtracking. We maintain a single StringBuilder object throughout the traversal.

```java
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);
    }
}
```
### Algorithm
1. Initialize empty result list
2. Create single StringBuilder for path building
3. 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

# Solutions
### Java

```java
/** * 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 ); } }
```

### CPP

```cpp
/** * 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 ; } };
```

### Python

```python
# 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 ans
```