• 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

We want every full route from the root down to a leaf, written out as a string. The interesting part is where the information lives.

      1
     / \
    2   3
     \
      5

  leaves are 5 and 3   ->   paths:  "1->2->5"   and   "1->3"

Read the picture: a path is only complete when it ends at a leaf (no children). Here 3 and 5 are leaves, so there are exactly two paths. Node 2 is not a leaf — it still has child 5 — so "1->2" is not an answer even though it is a real downward route.

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: the context you need flows down into the call as a parameter, not up out of it as a return value.

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 — do, descend, undo — is the signature of backtracking.

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 idea to keep: 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, a running total)? Pass parameters downward — pre-order. Here the thing flowing down happens to be the list of values on the route; swap that list for a single number and the very same shape solves a whole family of root-to-leaf questions. Once you can spot the direction, that's the real decision.