Binary Tree Paths
Binary Tree Paths: return every root-to-leaf path as strings like \"1->2->5\".
- The number of nodes in the tree is in the range [1, 100].
- -100 <= Node.val <= 100
Intuition
The binary tree paths problem asks for every root-to-leaf path, written out as strings like "1->2->5". The word every is the important one: this is not a search that stops at the first hit, it is an enumeration, and the output is as large as the number of leaves.
The natural fit is a depth-first traversal, because DFS follows one path from the root all the way down before backing up — which is exactly the shape of the thing you are collecting. As you descend, you carry the path built so far. When you reach a leaf, that path is complete and gets frozen into the result.
The one rule worth stating precisely is where a path ends:
- A path terminates at a leaf — a node with no children at all — not at a null pointer.
That distinction matters. If you emit whenever you hit null, a node with one child produces two copies of the same path, one through its real child and one through its missing one. Testing for a leaf before recursing avoids that entirely.
Binary tree paths is 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
Before reading on: price up what the direct approach costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(n·h) time and O(h) space.
Carry the path down the recursion
Define dfs(node, path) where path is the route from the root to this node's parent. Extend it with the current node's value on entry. Every call therefore knows its full history without needing parent pointers or a second traversal.
Emit only at a leaf
If the node has neither a left nor a right child, the path is complete — join it and add it to the results. Checking for a leaf rather than for null is what prevents duplicates on nodes that have exactly one child.
Recurse into whichever children exist
Call dfs on the left and right children when they are non-null. Guarding here rather than returning early inside the call keeps the leaf test above meaningful and avoids a wasted frame per missing child.
Choose between string copying and backtracking
Passing an immutable string down copies it at each level, costing O(h) per call but keeping the code trivially correct. The alternative is a shared list you append to before recursing and pop from afterwards — no copying, but forgetting the pop corrupts every later path.
Cost is dominated by the output
Every node is visited once, but each of the L leaves produces a string of length up to O(h), so the total is O(n · h) in the worst case. That is not inefficiency in the algorithm — it is simply the size of what was asked for, and no approach can beat it.
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.