Binary Tree Paths
Last Updated: March 29, 2026
Understanding the Problem
We need to find every path from the root of a binary tree down to a leaf node, and return each path as a string with node values separated by "->". A leaf is any node where both left and right children are null.
This is fundamentally a tree traversal problem. We need to visit every node, keep track of the path we took to get there, and whenever we hit a leaf, record that path. The trick is managing the path string as we go deeper and backing it up as we return from recursion.
The key observation is that this maps perfectly to depth-first search. As we recurse down from the root, we build up the path. When we reach a leaf, the current path is a complete root-to-leaf path. When we backtrack, we discard the last node from the path and try the other branch.
Key Constraints:
Number of nodes in [1, 100]→ With at most 100 nodes, any traversal approach is fast. Even O(n^2) gives us just 10,000 operations. The constraint guarantees at least 1 node, so we do not need to handle an empty tree.-100 <= Node.val <= 100→ Node values are small integers. They can be negative, which matters for string formatting (the "->" separator should not be confused with negative signs).
Approach 1: DFS with String Concatenation
Intuition
The most natural approach is to walk the tree with DFS, building up the path string as we go. At each node, we append the node's value to the current path. If the node is a leaf, that path is complete and we add it to our result list. If not, we recurse into the left and right children.
String concatenation in most languages creates a new string each time, so each recursive call works with its own copy of the path. This means backtracking is handled for free. When we return from a recursive call, the parent's path string is unchanged. No explicit "undo" step needed.
This is simple and works great for the given constraints. The downside is that creating new strings at every node means we are doing O(h) work per node (where h is the path length so far), leading to O(n * h) total time.
Algorithm
- Start DFS from the root with an empty path.
- At each node, append the node's value to the current path.
- If the node is a leaf (no left or right child), add the current path to the result list.
- If the node has a left child, recurse into the left child with the path followed by "->".
- If the node has a right child, recurse into the right child with the path followed by "->".
Example Walkthrough
Code
- Time Complexity: O(n * h). We visit every node exactly once. At each leaf, we finalize a path string of length up to h (the tree height). For a balanced tree this is O(n log n), for a skewed tree O(n).
- Space Complexity: O(n h). The recursion stack uses O(h) space. The output stores all paths, totaling O(n h) across all path strings.
The string concatenation approach creates a new string at every recursive call. What if we used a mutable list to track the path, and only built the string at leaf nodes?
Approach 2: DFS with Backtracking List
Intuition
Instead of creating a new string at every node, we can use a mutable list to accumulate the path. We append the current node's value as we go down, and explicitly remove it when we backtrack. This avoids creating new string objects at each recursion level.
The tradeoff is that we need to manage the undo step ourselves. With string concatenation, backtracking was free because each call had its own string. With a shared mutable structure, we must remember to remove what we added before returning. This is classic backtracking.
The backtracking list approach works because we maintain a single shared path that reflects exactly the nodes from the root to the current node at all times. When we go deeper, we push. When we come back up, we pop. This invariant means that at any leaf node, the list contains exactly the root-to-leaf path. The join operation at the leaf is the only place we allocate a new string.
Algorithm
- Start DFS from the root with an empty list to track the current path.
- At each node, add the node's value to the path list.
- If the node is a leaf, join the path list with "->" to form the path string and add it to the result.
- Recurse into the left child (if it exists).
- Recurse into the right child (if it exists).
- Remove the last element from the path list (backtrack).
Example Walkthrough
Code
- Time Complexity: O(n * h). We visit each node once. At each leaf, the join operation takes O(h) time. For a balanced tree this is O(n log n), for a skewed tree O(n).
- Space Complexity: O(n h). The recursion stack is O(h). The path list uses O(h) space. The output stores all path strings totaling O(n h).
Both approaches so far use recursion. What if we wanted to avoid the call stack entirely and use an iterative approach with an explicit stack?
Approach 3: Iterative DFS with Stack
Intuition
We can simulate the recursive DFS using an explicit stack. Instead of letting the call stack manage our traversal, we push pairs of (node, current path) onto our own stack. At each step, we pop a pair, and if the node is a leaf, we add the path to our result. Otherwise, we push the children with the extended path.
Since each stack entry carries its own path string, there is no shared mutable state and no need for explicit backtracking. The tradeoff is that we store path strings on the stack, which uses more memory than the backtracking list approach.
Algorithm
- Initialize a stack with the root node and its value as the initial path.
- While the stack is not empty, pop a (node, path) pair.
- If the node is a leaf, add the path to the result.
- If the node has a right child, push (right child, path + "->" + right child's value) onto the stack.
- If the node has a left child, push (left child, path + "->" + left child's value) onto the stack.
Example Walkthrough
Code
- Time Complexity: O(n h). We process each node once. At each node, string concatenation takes O(h) in the worst case. Total work across all nodes is O(n h).
- Space Complexity: O(n h). The stack can hold up to O(n) entries, each storing a path string of length up to O(h). The output also uses O(n h) space.