Thread

Two in-order traversals of one binary search tree, stepping together. On the left, the iterative version everyone writes: push down the left spine, pop to visit, step right, with the stack drawn as a column of cells beside the tree. On the right, Morris traversal — the one whose selling point is O(1) auxiliary space — with an identical column that stays empty the whole way.

The empty column is the setup. The payoff is what’s happening in the tree next to it. Before Morris descends into a left subtree it finds that subtree’s rightmost node — the current node’s in-order predecessor — and points that node’s unused right at the current node. That borrowed pointer is a thread, drawn here as a dashed arc curving back up, and it is the only reason the walk can find its way home. Come back to a node whose predecessor already threads to it and the left subtree is finished: cut the thread, put the pointer back exactly as it was, visit the node, step right.

So watch the two columns and then watch the strip under them, where cells held per step is drawn back to back at one scale — stack depth growing up, live threads growing down. The two silhouettes are the same shape, off by one. The stack did not disappear. It moved. Both walks have to remember the same chain of ancestors they still owe a visit to; the left one keeps that chain in memory it asked for, and Morris keeps it in pointer slots that happened to be lying around inside the data structure. On a left chain tree, stack depth 9 sits opposite 8 live threads drawn as eight parallel arcs you can count. On a right chain there is nothing to come back to, so the stack never exceeds 1 and Morris never threads at all — it is free, and exactly as free as the other one.

Two things that cost real money, both on screen:

• The tree is broken while you read it. Every live thread is an edge pointing back up, so following right pointers from a leaf goes in a circle. The readout says so at every step where a thread exists. A reader arriving mid-walk does not see a slow tree, it sees a cyclic one — which is why this trick is fine in a single-threaded interview answer and a menace in shared, concurrent, or reentrant code, and why it can’t be used on a tree you only hold a const reference to.
• Threading costs walks. Finding the predecessor means walking a right spine, and cutting the thread means walking it again, so most edges get crossed three times. Link reads are counted under each pane: Morris runs about 2× the stack version on a balanced tree.

And at the end, the thing worth proving rather than asserting: the two trees are drawn identically and the tree’s fingerprint — every node, every link — is compared against the one taken before the walk started. Restored exactly, 14 pointer writes later.

Reuse

src/thread.js is a framework-free ES module:

• makeTree(n, { shape, rand }) — a BST over the keys 1..n, so in-order output is always 1, 2, 3, … and only the route is in question. Shapes: balanced, random, left-chain, right-chain, vee (a left chain and a right chain joined at the root — one half threads at every step, the other never threads at all). treeFromKeys takes an explicit insertion order.
• traceStack(tree) / traceMorris(tree) — one frame per move, both in the same vocabulary: { action, cur, note, emitted, out, stack, threads, path, aux, auxPeak, links, writes, done }. threads is the live [from, to] pairs; path is the nodes re-walked on that step, which is where Morris’s extra link reads come from. Same trace-per-tick shape as rho, sift and window.
• simulate(tree) — both traces plus the numbers worth putting side by side.
• fingerprint(tree) — root, keys and links as a string. traceMorris takes one before it starts and one after it ends, and reports restored.

traceMorris works on its own copy of the nodes, so calling it does not mutate the tree you passed in. No rendering or timers in the module; the canvas demo is reference code.

Gotchas

• The panes step by moves, not by time. One frame each per tick, and a Morris move can hide a walk down a right spine, so Morris often emits keys ahead of the stack pane while reading twice as many links. The link counter is the honest race; the output rows are not. The demo says this under the counters.
• Morris only ever writes to a right that is null, so a real edge is never overwritten and the renderer can draw the original tree plus the live threads. That is also why the restore is exact rather than best-effort.
• Peak threads is stack depth minus one in the usual case, not equal to it: the node currently being stepped into is held in a variable rather than threaded. The back-to-back strip shows the offset instead of hiding it.
• The demo bundles its own copy of thread.js (self-contained by contract); re-copy after editing src/.
• node scripts/screenshot-demo.mjs [out] [--shape=] [--nodes=] [--at=end] regenerates thumb.png and the shots in media/ through site/scripts/lib/chromium.mjs.