Intuition
DFS carrying the path so far. At a leaf, freeze the path into a string. Passing the accumulated string down each call (or a list with push/pop backtracking) enumerates each path exactly once.
Root-to-leaf enumeration. Because strings are immutable in Python, passing prefix + "->" gives you backtracking for free — each branch receives its own copy and there is nothing to undo. That's worth recognising: when the accumulator is immutable, the explicit pop of a normal backtracking loop disappears.
Approach
Carry the prefix
dfs(node, prefix): extend prefix with node.val; at a leaf, emit.
Leaf is the emit point
Only nodes with no children terminate a path — internal nodes just pass through.
Strings vs backtracking
String concatenation copies per call (fine for output-sized work); a shared list with pop() after recursion avoids copies.
Solution & live demo
Common pitfalls
Building the path in a shared list without undoing
path.append(str(node.val)) dfs(node.left) dfs(node.right)
dfs(node.left, prefix + "->") dfs(node.right, prefix + "->")
A shared list carries nodes from abandoned branches into unrelated paths unless every append is matched by a pop. Passing an immutable string sidesteps the whole class of bug — each call frame owns its prefix.
Appending the arrow after the leaf
prefix += str(node.val) + "->"
if not node.left and not node.right:
res.append(prefix)prefix += str(node.val)
if not node.left and not node.right:
res.append(prefix); return
dfs(node.left, prefix + "->")Every recorded path would end with a trailing "->". The separator belongs between values, so it's added when descending to a child — not after writing a node.
Recording at every node instead of at leaves
prefix += str(node.val) res.append(prefix)
if not node.left and not node.right:
res.append(prefix); returnThe problem asks for root-to-leaf paths, so partial paths ending at internal nodes don't count. Recording everywhere returns every prefix of every path.
Edge cases
Root is a leaf → ["root"].
Not a leaf — path continues through the existing child only.