Binary Tree Paths: DFS Path Building

Given the root of a binary tree, return all root-to-leaf paths in any order. Each path should be represented as a string with node values separated by "->".

This is Binary Tree Paths (LeetCode 257), and it is a natural extension of the pre-order state passing pattern you see in Path Sum. Instead of carrying a number downward and checking a condition at the leaf, you carry a string downward and collect it at the leaf. The core recursion is nearly identical.

The approach

You use depth-first search to walk through every root-to-leaf path. At each node, you extend the current path string by appending "->" followed by the node's value. When you reach a leaf (a node with no children), the path string is complete, and you add it to your result list.

The recursion has three parts:

1. Start at the root. Initialize the path with the root's value as a string.
2. At each non-leaf node, recurse into any existing children. Pass the extended path string down.
3. At a leaf node, add the current path to the result list and return.

Because you build a new string at each recursive call (using concatenation rather than mutation), you do not need to undo anything when backtracking. Each branch of the recursion carries its own copy of the path.

The solution

def binary_tree_paths(root):
    if not root:
        return []
    result = []
    def dfs(node, path):
        if not node.left and not node.right:
            result.append(path)
            return
        if node.left:
            dfs(node.left, path + "->" + str(node.left.val))
        if node.right:
            dfs(node.right, path + "->" + str(node.right.val))
    dfs(root, str(root.val))
    return result

Here is what each piece does:

• if not root: return [] handles the empty tree. No nodes means no paths.
• result = [] collects the finished path strings.
• dfs(node, path) is the recursive helper. It receives the current node and the path string built so far.
• The leaf check if not node.left and not node.right fires when the node has no children. At that point, path holds the complete root-to-leaf string, so you append it to result.
• The two if blocks recurse into the left and right children (if they exist), extending the path string each time.
• dfs(root, str(root.val)) kicks off the recursion from the root, starting the path with the root's value.

Step-by-step walkthrough

Let's trace through the tree [1, 2, 3, null, 5] and watch how the path string grows at each level.

The key observation is that each recursive call builds its own path string. When the DFS reaches node 5, the path is "1->2->5". When it reaches node 3, the path is "1->3". There is no shared mutable state, so backtracking happens automatically through the call stack.

Complexity analysis

Time is O(n) because every node is visited exactly once during the DFS traversal. At each leaf, you also copy the path string, which can be up to O(n) characters long. In the worst case (a balanced tree with n/2 leaves), the total string copying work is O(n log n). For a skewed tree (one leaf), it is O(n).

Space is O(n). The recursion stack can grow up to O(n) deep for a skewed tree. The result list stores all paths, and the total characters across all paths is O(n log n) for a balanced tree. The dominant term is O(n) for the stack and output combined.

Building blocks

This problem combines two fundamental techniques:

1. Pre-order state passing. You carry state (the path string) from parent to child as you descend through the tree. At each node, you transform the state by appending the child's value. At a leaf, you use the accumulated state. This is the same pattern used in Path Sum (where the state is a remaining target) and Sum Root to Leaf Numbers (where the state is a running digit).

2. String building through concatenation. Instead of using a mutable list and manually undoing changes when backtracking, you build a new string at each recursive call with path + "->" + str(child.val). Python strings are immutable, so each call gets its own copy. This trades a small amount of memory for simplicity. You never need to pop or undo anything.

The skeleton for this family of problems looks like:

def solve(root):
    result = []
    def dfs(node, state):
        if is_leaf(node):
            result.append(state)
            return
        for child in children(node):
            dfs(child, extend(state, child))
    dfs(root, initial_state(root))
    return result

For Binary Tree Paths, initial_state is str(root.val), extend is path + "->" + str(child.val), and is_leaf checks that both children are None.

Edge cases

• Empty tree (root is None). Return an empty list. There are no nodes, so there are no paths.
• Single node (root is a leaf). Return [str(root.val)]. The root is both the start and end of the only path. The leaf check triggers immediately.
• Skewed tree (every node has only one child). There is exactly one root-to-leaf path. The DFS follows it all the way down, building one long string like "1->2->3->4->5".
• Complete binary tree. Every leaf produces a path. A tree with n nodes has roughly n/2 leaves, so the result list has about n/2 entries.
• Negative values. The algorithm handles them naturally. Negative numbers convert to strings with a minus sign, producing paths like "1->-2->3".

From understanding to recall

You just watched the DFS build path strings as it descends through a tree. The pattern is clear: carry the path down, collect it at the leaves, and let immutable string concatenation handle the backtracking for you.

But will you remember this cleanly in an interview? Will you know to check if not node.left and not node.right for the leaf case? Will you remember to start the path with str(root.val) and only append the arrow when recursing into children?

Spaced repetition builds that recall. You type the solution from scratch at increasing intervals: after a day, then three days, then a week. Each time, you reconstruct the DFS helper, the leaf check, and the string extension from memory. After a few rounds, the pre-order state passing pattern becomes automatic.

Pre-order state passing is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Path Sum - The same pre-order state passing pattern, but you carry a number instead of a string and return a boolean instead of collecting paths
• Maximum Depth of Binary Tree - Foundational tree recursion that collects results going back up instead of passing state down
• Same Tree - Another clean tree recursion problem that shows parallel traversal with base case checks