Inorder traversal normally needs a stack (or recursion’s call stack) — O(h) extra space — to remember how to get back up after visiting a left subtree. Morris traversal removes that cost entirely by borrowing the tree itself: before descending left, it wires the subtree’s rightmost node (the inorder predecessor) with a temporary thread pointing back to the current node. When the traversal returns along that thread, it knows to visit and then undo the thread, leaving the tree exactly as it found it. Step through and watch the threads flicker in and out.
O(n) time · O(1) extra space · no stack, no recursion, tree restored
inorder
Left subtree, node, right subtree — for a BST this yields sorted order.
predecessor
The rightmost node of a node’s left subtree — the value visited just before it.
thread
A temporary right pointer from a predecessor back to its node, used to climb back up.
restore
On the second visit to a node, the thread is removed — the tree ends unchanged.
morris.js — borrow a pointer, then give it back
Ready
A binary search tree. We inorder-traverse it with no stack: before going left, thread the left subtree’s rightmost node back to here; follow that thread later to climb back. Step through the loop.
4
at node
0
live threads
O(1)
extra space
output:
How it works
The single idea is that a leaf’s unused right pointer is free storage. A node’s inorder predecessor is the rightmost node of its left subtree, and that node’s right pointer is null — nowhere to go. Morris borrows it: point it back at the current node so that when the left subtree finishes, following that right pointer lands exactly where the traversal needs to resume. Seeing the thread already in place on a second visit is the signal to undo it and move right.
1
No left child? Visit and go right
If the current node has no left subtree, there’s nothing to defer — visit it (emit its value) and move to its right pointer.
2
Has a left child? Find the predecessor
Walk to the rightmost node of the left subtree. That node is the inorder predecessor of the current node.
3
First visit: thread and go left
If the predecessor’s right is null, set it to point back to the current node (create the thread) and descend into the left subtree.
✓
Second visit: unthread, visit, go right
If the predecessor’s right already points back here, the left subtree is done. Remove the thread (restore the tree), visit the current node, and move right. Every thread created is undone.
Time
O(n)
Extra space
O(1)
Stack / recursion
None
Tree after
Unchanged
The code
# inorder traversal, O(1) extra space, tree restoreddef morris_inorder(root):
cur, out = root, []
while cur:
ifnot cur.left:
out.append(cur.val); cur = cur.right # visit, go rightelse:
pre = cur.left
while pre.right and pre.right isnot cur:
pre = pre.right # rightmost = predecessorif pre.right isNone:
pre.right = cur; cur = cur.left # thread, descend leftelse:
pre.right = None# unthread (restore)
out.append(cur.val); cur = cur.right # visit, go rightreturn out
Quick check
1. What extra space does Morris traversal use?
Morris uses only a couple of pointers — O(1). Instead of a stack, it borrows the null right pointer of each inorder predecessor as a temporary thread to climb back up, then removes it.
2. When a node has a left child, what does Morris do first?
It walks to the rightmost node of the left subtree — the inorder predecessor. Depending on whether that node’s right is null or already threaded back, it either creates the thread and goes left, or removes it and visits.
3. What is the state of the tree after Morris traversal finishes?
Every thread created on a first visit is removed on the corresponding second visit, so the tree ends structurally identical to how it began. This restoration is a defining property of Morris traversal.
FAQ
What is Morris traversal?
An algorithm that traverses a binary tree inorder using O(1) extra space — no stack, no recursion. It temporarily threads each inorder predecessor’s right pointer back to its node, uses those threads to climb back up, and removes each one so the tree ends unchanged.
How does Morris traversal avoid using a stack?
Normal inorder needs a stack to remember how to return after a left subtree. Morris stores that return path in the tree itself — pointing the left subtree’s rightmost node (whose right pointer is unused) back at the current node. Following it later returns to the right place, so no stack is needed.
What is the downside of Morris traversal?
It temporarily mutates the tree (adding threads), so it’s not safe under concurrent reads or on an immutable tree, and it’s trickier to get right than a stack-based traversal. Some nodes are visited twice (thread, then unthread), though total work stays O(n).
When would you use Morris traversal?
When you need strict O(1) extra space — very deep trees where an O(h) stack is too costly, or memory-constrained environments. In everyday code a recursive or stack-based traversal is clearer and usually preferred.