02
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.
03
Approach
1
Carry the prefix
dfs(node, prefix): extend prefix with node.val; at a leaf, emit.
2
Leaf is the emit point
Only nodes with no children terminate a path — internal nodes just pass through.
3
Strings vs backtracking
String concatenation copies per call (fine for output-sized work); a shared list with pop() after recursion avoids copies.
04
Solution & live demo
python
▶1class Solution:
▶2 def binaryTreePaths(self, root):
▶3 res = []
▶4 def dfs(node, prefix):
▶5 if not node: return
▶6 prefix += str(node.val)
▶7 if not node.left and not node.right:
▶8 res.append(prefix); return
▶9 dfs(node.left, prefix + "->")
▶10 dfs(node.right, prefix + "->")
▶11 dfs(root, "")
▶12 return res
05
Edge cases
Single node
Root is a leaf → ["root"].
Node with one child
Not a leaf — path continues through the existing child only.
06
Complexity
Time
O(n·h)
Space
O(h)
Each path string costs its length.