Morris Inorder Traversal
Inorder traversal in O(1) space — no recursion, no stack.
- 1 <= number of nodes <= 10⁵
- -10⁹ <= node value <= 10⁹
- O(1) auxiliary space — no recursion and no stack
Intuition
Morris inorder traversal walks a binary tree in sorted order using O(1) extra space — no recursion and no explicit stack. That sounds impossible, since traversal fundamentally needs a way back up after descending, and the usual answer is to store ancestors somewhere. Morris's move is to store that return path inside the tree itself, temporarily. Before descending into a left subtree, find that subtree's rightmost node — which is the current node's inorder predecessor — and point its unused right pointer back at the current node. That borrowed link is a thread, and it is the breadcrumb that replaces the stack frame. When the left subtree is exhausted, following that thread returns you to where you started, and its very existence is the signal that carries the information: - No thread yet means the left subtree is unvisited — create the thread and descend left. - A thread already pointing here means the left subtree is finished — cut it, visit the node, and go right. Cutting the thread is not tidiness; it is what leaves the tree in its original shape and prevents an infinite loop on a later pass. The cost looks worse than it is. Finding each predecessor walks a right spine, which appears to add a factor — but each edge is traversed at most three times across the whole run, so the total stays O(n). The preorder variant is the same algorithm with the visit moved to the first arrival instead of the second.
O(1) space by borrowing the tree's own null pointers. Each node's inorder predecessor has a free right pointer; temporarily aiming it at the current node creates a thread back up, removing the need for a stack. Arriving via that thread is the signal that the left subtree is finished.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(1) space.
Understand what a thread replaces
A thread is a temporary right pointer from a left subtree's rightmost node back to the current node. It stands in for the stack frame an ordinary traversal would push, which is the entire source of the O(1) space bound.
Handle a missing left child directly
If the current node has no left child, its inorder position is now — visit it and move right. No threading is needed, and on a right-skewed tree this is the only branch ever taken.
Find the inorder predecessor
Step to node.left, then follow right pointers as far as they go. Stop when the right pointer is null or already points back at the current node — that second condition is what distinguishes a first arrival from a second.
First arrival: thread and descend
If the predecessor's right is null, this is the first visit. Set that pointer to the current node and move left without visiting — inorder requires the left subtree to be emitted first.
Second arrival: cut, visit, go right
If the predecessor's right already points here, the left subtree is complete. Set that pointer back to null to repair the tree, visit the node now, and move right. Skipping the repair leaves a cycle in the tree.
See the preorder difference
Morris preorder is this same machinery with the visit moved into the first-arrival branch, since preorder emits a node before its left subtree. Only the placement of the visit changes — the threading is identical.
Cost of the threaded walk
Each edge is traversed at most three times — descending, threading, and returning — so despite the predecessor searches the total is O(n) time with genuine O(1) space, and the tree is left exactly as it was found.
Solution & live demo
Common pitfalls
Not cutting the thread
else:
res.append(cur.val)
cur = cur.rightelse:
pred.right = None
res.append(cur.val)
cur = cur.rightThe thread is scaffolding, not structure. Leaving it in place permanently corrupts the tree into a cyclic graph, so any later traversal loops forever.
Omitting the pred.right is not cur check
while pred.right:
pred = pred.rightwhile pred.right and pred.right is not cur:
pred = pred.rightOn the second visit the predecessor's right pointer is the thread, pointing back at cur. Without the identity check the walk follows it and spins in an infinite loop.
Emitting the value on first arrival
if not pred.right:
res.append(cur.val)
pred.right = curif not pred.right:
pred.right = cur
cur = cur.leftThat produces Morris preorder. Inorder requires the node to be emitted only when returning via the thread, after its entire left subtree has been output.
Edge cases
Visit immediately and go right — the trivial case.
Threads would be left dangling — Morris must run to completion to restore the tree.