Community Problem
Binary Tree Paths
Difficulty: Easy
Return every root-to-leaf path in a binary tree as a list of arrow-joined strings.
Binary Tree Paths
Return every root-to-leaf path in a binary tree as a list of arrow-joined strings.
By CodeSnatch
January 29, 2026
·
Updated May 20, 2026
813 views
14
4.5 (10)
Onboarding a junior on tree recursion last quarter, this is the problem I leaned on after Invert Binary Tree clicked. The official catalog has DFS-on-tree problems, but it skipped the cleanest one for teaching the path-accumulator pattern: how do you carry a partial answer down the recursion stack without mutating it on the way back up? That is the entire lesson here.
Binary Tree Paths
Given the root of a binary tree, return all root-to-leaf paths in any order. Each path is rendered as a string of node values joined by "->". A leaf is a node with no children.
Examples
Example 1:
- Input:
root = [1, 2, 3, null, 5] - Output:
["1->2->5", "1->3"] - Explanation: Two leaves, two paths. The leaf at value
5traces back through2and1; the leaf at value3traces directly through1.
Example 2:
- Input:
root = [1] - Output:
["1"] - Explanation: A single-node tree is itself a leaf, so the only path is the one-element string
"1".
Example 3:
- Input:
root = [1, 2] - Output:
["1->2"] - Explanation: A degenerate left chain has one leaf and therefore one path.
Example 4:
- Input:
root = [10, 20, 30, 40, 50, 60, 70] - Output:
["10->20->40", "10->20->50", "10->30->60", "10->30->70"] - Explanation: A perfect tree of depth 3 produces exactly four root-to-leaf paths.
Constraints
- The number of nodes in the tree is in the range
[1, 100]. -100 <= Node.val <= 100.
Follow-up
Can you do it iteratively with an explicit stack of (node, pathSoFar) pairs? When does that pay off versus the recursive version?
Solution
Hints
Solution Walkthrough
Approach: DFS with a Mutated Path Accumulator (O(n) time, O(h) space)
The naive idea is to pass an immutable string down the recursion. That works, but it is O(h) string construction per recursive call, which is O(n * h) total. The cleaner pattern carries a single path array, mutates it on the way down, and pops on the way back up. Only at leaves do we materialize the joined string.
Algorithm
- If
rootisnull, return an empty list. - Initialize
result = []andpath = []. - Recurse into
dfs(node):- Push
node.valontopath. - If
nodeis a leaf (both children null), pushpath.join('->')ontoresult. - Otherwise, recurse into the non-null children.
- Pop
node.valoffpathbefore returning.
- Return
result.
Why It Works
The push-then-pop discipline guarantees that on entry to any recursive call, path contains exactly the values along the current root-to-current-node trail. That invariant is what lets the leaf check produce a correct path string with one join. The base-case if (root === null) guard handles the empty tree; the inner if (node.left !== null) guards skip recursion into absent children so a single leaf does not get treated as two recursive nulls.
Complexity
Sample binary tree
1
/ \
2 3
\
5Metric Value
Time O(n) where n is the node count; each node is visited once
Space O(h) recursion stack + O(n) result; for a balanced tree h = log nPitfalls
- String concatenation per level. Building a new string at every recursive call (
dfs(node, prefix + '->' + node.val)) is correct but wasteful. Mutating a shared array and joining only at leaves is the cleaner pattern. - Forgetting the pop. If you push without popping, sibling subtrees will see polluted prefixes and the output will contain bogus paths.
- Treating null children as leaves. A node with one child is NOT a leaf. The leaf check must require BOTH children to be null. A common bug is to recurse into both children unconditionally, hit a null on one side, and emit a duplicate path.
Solution Code