Morris Traversal (Inorder and Preorder)
WHAT IT SAYS
Traverse a binary tree inorder (or preorder) using O(1) extra space — no recursion stack, no explicit stack.
WHAT IT'S REALLY ASKING
"The stack exists for exactly one reason: before diving into a left subtree, you must remember how to get back. But look at where a left subtree FINISHES — at its rightmost node, whose right pointer is null and pointing at nothing. Free memory, sitting at precisely the spot where the walk will need directions home. Why carry a stack when the tree has empty pockets exactly where you need them?"
Recursion, or an explicit stack
O(n) time, O(h) space — which is O(n) on a skewed treeInorder: recurse left, visit, recurse right — or simulate it with a stack, pushing nodes on the way down-left and popping to visit before turning right. Correct, canonical, and what you should write in 99 percent of real code.
WHERE THE WORK IS WASTED — Interrogate what each stack frame actually stores: a pointer to an ancestor you must revisit after its left subtree completes. That is all — a return address. Now notice the tree's own accounting: n nodes own 2n child pointers but only n-1 edges exist, so n+1 pointers hold null. The information the stack carries (one return address per pending ancestor) is SMALLER than the free space the structure already contains, and the free slots even sit in the right places. The stack is external storage rented for data the building has empty rooms for.
A predecessor's null right pointer is a free return address.
Where does an inorder walk go immediately after finishing a left subtree? To the subtree's root — the ancestor the stack was remembering. And which node is the LAST one visited inside that left subtree? Its rightmost node: the current node's inorder predecessor. That predecessor's right pointer is null — it is the subtree's bottom-right corner, nothing hangs there. So the walk's return address has a natural home: thread predecessor.right to point back at the current node, and the walk can find its way home with no stack at all. The loop then needs no memory beyond one cursor. At each node with a left child, walk down to its predecessor (left once, then right until the thread-or-null). Two cases, and this case split is the entire algorithm: Predecessor's right is null — first arrival. Plant the thread (predecessor.right = current), then descend left. The thread is a promise: when the left subtree finishes, it will deliver the walk back here. Predecessor's right already points at current — second arrival, meaning the thread you planted has just been used: the left subtree is COMPLETE. Remove the thread (restore the null), visit the current node, and move right. The thread's existence is itself the visited-flag: no marks, no sets, the temporary edge encodes 'left side done'. A node with no left child is visited immediately and the walk moves right — possibly along a thread, which is exactly the mechanism working. Preorder is a one-line reshuffle that is worth understanding rather than memorising: the ONLY difference from inorder is WHEN the visit happens relative to the thread. Inorder visits on the second arrival (after the left subtree); preorder visits on the FIRST arrival, at the moment of planting the thread, because preorder's contract is root-before-left-subtree. Same threads, same two cases, the emit statement moves from one branch to the other. Two honesty notes. Each edge near the right spine of every left subtree is walked at most three times (down, predecessor-search, return), so time stays O(n) — amortised, the predecessor searches sum to the tree size. And the tree is temporarily NOT a tree: while threads exist, there are cycles, so the structure is unsafe for concurrent readers until the walk completes and restores every null.
Thread, descend, detect, unthread
O(n) time — each edge traversed a constant number of times — O(1) spacecursor = root. Loop: if no left child, visit and go right. Otherwise find the predecessor (left once, right until null-or-cursor). If its right is null: thread it to cursor (for preorder, visit NOW), go left. If its right is cursor: unthread it (for inorder, visit NOW), go right. Stop when the cursor runs off the tree — every thread has been removed by its own second-arrival case.
Borrow the Structure's Free Slots
YOU'LL SEE IT AGAIN WHEN
- The auxiliary memory (stack, visited set) stores only return-addresses or flags — information proportional to the structure's own unused capacity (n+1 null pointers in any n-node binary tree).
- There is a natural rendezvous: the walk's return target and a free slot coincide (the predecessor's null right points exactly where the walk resumes).
- The borrowed slot's occupied-versus-free state can double as the visited flag, so detection and storage are the same mechanism.