• The number of nodes in the tree is in the range [1, 100]
• -100 <= Node.val <= 100
• Every returned path starts at the root and ends at a leaf
• Order of the returned paths does not matter

Everything so far has computed a single number by letting information travel upward: a node asked its children for their answers and combined them. This problem is the first that cannot work that way, and seeing why is the whole point.

A leaf cannot say anything useful about "the path from the root to me." It has no idea what the root is, or which turns were taken to reach it. The information a leaf needs — the sequence of values above it — exists only in its ancestors. So it has to be handed down, as an extra argument travelling with the recursive call. That is the other half of the pair introduced in Maximum Depth: results come up as return values, context goes down as parameters.

Give the recursive function a second argument: the path built so far, not yet including the current node. Then one node's job is small.

Because the extension has to happen before the children are called (they need it), the work sits in the slot before the recursion — a pre-order shape. That is not a style choice: children literally cannot run without the value.

out = []

def walk(node, path):
    if node is None:
        return
    path = path + [node.val]                 # extend — a NEW list, see the note below
    if node.left is None and node.right is None:
        out.append("->".join(map(str, path)))   # a leaf: this path is complete
        return
    walk(node.left, path)
    walk(node.right, path)

walk(root, [])
return out

The line path = path + [node.val] builds a brand-new list at every node. That is safe — each call owns its own copy, so a sibling can never see another sibling's additions — but it copies up to H values per node, so the copying alone costs O(N × H).

The alternative is to keep one list for the entire traversal, shared by every call. Then it must be repaired on the way out, because after finishing the left subtree that shared list still has all the left subtree's values sitting in it, and the right child would inherit garbage. So: append your value before descending, and remove it after both children return.

path = []

def walk(node):
    if node is None:
        return
    path.append(node.val)                   # entering: I am on the route
    if node.left is None and node.right is None:
        out.append("->".join(map(str, path)))
    else:
        walk(node.left)
        walk(node.right)
    path.pop()                              # leaving: undo, so siblings start clean

This add-on-entry, remove-on-exit discipline is called backtracking, and the invariant it maintains is worth saying out loud: at any instant, path holds exactly the nodes on the route from the root to the node currently being processed — nothing more. The pop is what makes that true; without it the list only ever grows and every recorded path is polluted with branches that were abandoned. Notice that the append happens before the calls and the pop after them, so the same function has work in both the pre-order and post-order slots. That combination is the signature of backtracking, and you will meet it again throughout the backtracking section with subsets and permutations.

Watch the moment after 5 is recorded: if the pops were missing, node 3 would have inherited [1, 2, 5] and emitted "1->2->5->3", a route that does not exist in the tree. The undo step is not tidiness, it is correctness.

Each node is visited once, so the traversal itself is O(N). But the output is not a single number — it is one string per leaf, each up to H characters, so simply writing the answer takes O(N × H) in the worst case, and no algorithm can be faster than its own output. Space is O(H) for the recursion and the shared path, plus the output itself. With the copying version, the copies also cost O(N × H), which is why backtracking is preferred once paths get long.

The generalisation to carry forward: decide what each node needs, then decide which direction that information flows. Needs facts about its own subtree (height, sum, validity) → return values upward, post-order. Needs facts about its ancestry (the route taken, the depth, an accumulated total) → pass parameters downward, pre-order. Path Sum is the same downward flow with a running total instead of a list; Root to Node Path is the same backtracking with an early exit as soon as the target is found; Sum Root to Leaf Numbers carries a number down instead of a sequence. Once you can spot the direction, these stop being separate problems.