• The number of nodes in the tree is in the range [0, 10⁵]
• -100 <= Node.val <= 100
• O(1) auxiliary space — the output list does not count
• The tree's structure must be fully restored before you return

Every traversal so far has needed somewhere to remember the way back. Recursion used the call stack; the iterative version used a stack we allocated ourselves. Both cost O(H), and on a chain-shaped tree that is O(N). The question here is whether the remembering can be avoided altogether.

The obstacle is precise. In-order means: finish the left subtree, then emit this node, then do the right subtree. Once you descend into the left subtree, links only lead further downward — there is no way back up to the node you still owe an emission to. That single missing return route is the entire reason a stack exists.

Count them. A tree with N nodes has 2N pointer slots and only N - 1 of them point at anything, so N + 1 slots sit empty. That is more empty slots than nodes. If one of them could be made to point back where we need to return, the stack becomes unnecessary.

Which slot? Ask where we will be standing at the exact moment we need to come back to node v. We need to return to v right after its left subtree is finished — that is, immediately after the last node the in-order walk visits inside that subtree. In-order finishes a subtree at its rightmost node, so that node is v's in-order predecessor: go once into v.left, then follow right links as far as they go.

And now the fact that makes everything work: that rightmost node's right pointer is, by definition, empty — it is rightmost precisely because it has nothing to its right. So there is a free slot sitting exactly where we need one. Point it at v, and when the walk falls off the end of the left subtree it lands back on v automatically, with no memory required.

A link we invent is not part of the tree, so it has to be removed before we finish — and removing it is also how we detect that we have already been down that way.

Standing on curr:

Each node with a left child is therefore reached twice — once going down, once coming back — and the state of the predecessor's pointer is what distinguishes the two visits. That is the same information a stack was storing, kept inside the tree instead of beside it.

out, curr = [], root
while curr:
    if curr.left is None:
        out.append(curr.val)             # nothing owed on the left
        curr = curr.right                # real edge or borrowed thread
    else:
        pred = curr.left                 # find the in-order predecessor
        while pred.right and pred.right is not curr:
            pred = pred.right
        if pred.right is None:
            pred.right = curr            # borrow: leave a way back
            curr = curr.left             # descend, emitting nothing yet
        else:
            pred.right = None            # give it back — the tree is restored here
            out.append(curr.val)         # left subtree done, so emit now
            curr = curr.right

Extra space is O(1) — two pointers, regardless of the tree's size or shape. Time is still O(N), though it takes an argument: the predecessor searches walk some edges repeatedly, but each edge is walked at most three times in total (once descending, once during the predecessor search that installs a thread, once during the search that removes it), so the work stays proportional to the number of edges.

The price is real and worth stating: the code is longer and much easier to get wrong than a four-line recursion, and it temporarily mutates the tree, which rules it out for shared or read-only structures. Reach for it when the height is genuinely unbounded and memory is genuinely tight — otherwise the recursive or explicit-stack versions are better engineering.

The idea that transfers is bigger than this algorithm: unused capacity in a data structure can substitute for auxiliary memory. The same instinct produces threaded binary trees, the XOR-linked list, the O(1)-space rewiring in Flatten Binary Tree, and cycle-detection tricks that mark visited nodes in place. Whenever an algorithm needs to remember something, it is worth asking whether the structure itself has room to hold that memory — and, just as importantly, whether you can put it back.