Binary Tree Paths
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 maps directly to depth-first search. As the traversal descends from the root, it extends the current path. Every leaf it reaches marks a complete root-to-leaf path to record. The work of the problem is managing the path state: extending it on the way down and discarding the last node on the way back up before trying the other branch.
Key Constraints:
Number of nodes in [1, 100]→ With at most 100 nodes, any traversal approach is fast enough. The constraint guarantees at least 1 node, so the tree is never empty, though defensive null checks cost nothing.-100 <= Node.val <= 100→ Values can be negative, so a valid path can look like "-1->-2". Standard integer-to-string conversion produces the minus sign correctly, so no special casing is needed.
Approach 1: DFS with String Concatenation
Intuition
Walk the tree with DFS, building up the path string as we go. At each node, append the node's value to the current path. If the node is a leaf, that path is complete and goes into the result list. If not, recurse into the left and right children.
String concatenation creates a new string each time, so each recursive call works with its own copy of the path. When a call returns, the parent's path string is unchanged, which means no explicit undo step is needed.
The cost of that convenience is allocation. Copying the path at a node of depth d takes O(d) work, so total time grows with the sum of all node depths rather than the node count alone.
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 and return.
- Otherwise, append "->" to the path and recurse into both children. A null child returns immediately at the top of the call.
Example Walkthrough
Code
- Time Complexity: O(n * h), where h is the tree height. Every visit copies a path string proportional to the node's depth. For a balanced tree this totals O(n log n); for a skewed tree, h = n and the copying totals O(n^2).
- Space Complexity: O(n h). The recursion stack uses O(h) space (O(n) worst case for a skewed tree). The output stores all paths, totaling O(n h) across all path strings in the worst case.
Approach 1 allocates a new path string at every node. The next approach keeps one mutable list for the whole traversal and builds a string only at the leaves.
Approach 2: DFS with Backtracking List
Intuition
Instead of creating a new string at every node, we can use a single mutable list to accumulate the path. We append the current node's value as we go down, and explicitly remove it when we backtrack. At a leaf, joining the list with "->" produces the path string, and that join is the only string allocation in the traversal.
The tradeoff is that the undo step is now ours to manage. With string concatenation, each call held a private copy of the path, so returning required no cleanup. With a shared mutable list, whatever a call appends it must remove before returning. This is the standard backtracking pattern.
Every call appends exactly one value on entry and removes exactly one value before returning. Between those two points, the list holds precisely the values from the root to the current node, so when the current node is a leaf, joining the list yields the complete root-to-leaf path.
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 + s), where s is the total length of all output strings. Each node contributes O(1) list work (one append, one removal); strings are built only at leaves, costing O(path length) per leaf. For a skewed tree s = O(n), and for a balanced tree s = O(n log n). This is the improvement over Approach 1, which also pays string-copy costs at internal nodes.
- Space Complexity: O(h) extra, for the recursion stack and the path list (O(n) worst case for a skewed tree), plus the O(s) output.
Both approaches so far recurse, which limits the maximum tree depth to the size of the call stack. An explicit stack removes that limit.
Approach 3: Iterative DFS with Stack
Intuition
We can simulate the recursive DFS with an explicit stack. Instead of letting the call stack manage the 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 the result. Otherwise, we push the children with the extended path.
Each stack entry carries its own path string, so there is no shared mutable state and no explicit backtracking. The tradeoff is that path strings sit on the stack alongside the nodes, which uses more memory than the backtracking list, and the per-node concatenation brings back the copying cost of Approach 1.
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), where h is the tree height. We process each node once, and the concatenation when pushing a child copies a string proportional to that child's depth. As in Approach 1, this totals O(n log n) for a balanced tree and O(n^2) for a skewed one.
- 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 in the worst case.