Morris Inorder Traversal
Inorder traversal in O(1) space — no recursion, no stack.
Open on GeeksforGeeks ↗Intuition
The stack's only job is remembering how to get back up. Morris threading stores that return path in the tree itself: link the left subtree's rightmost node (the inorder predecessor) back to the current node. Coming back later, the thread's existence tells you the left side is done — remove it and visit.
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
Find the predecessor
cur has a left child → walk left subtree's right spine to its end (stopping if the thread back to cur already exists).
Thread or visit
No thread yet → create it (pred.right = cur), descend left. Thread exists → left subtree finished: cut the thread, visit cur, go right.
Tree restored
Every thread is removed on second arrival — the tree ends unchanged, and each edge is walked ≤ 3 times → O(n).
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.