Morris Preorder Traversal
Preorder traversal in O(1) space using Morris threading.
- 1 <= number of nodes <= 10⁵
- -10⁹ <= node value <= 10⁹
- O(1) auxiliary space — no recursion and no stack
Intuition
Morris preorder traversal walks a binary tree in preorder using O(1) extra space — no recursion, no explicit stack. That sounds impossible at first, because traversal fundamentally needs a way to get back up after descending, and the usual answer is to remember ancestors somewhere. Morris's insight is to store that return route inside the tree itself, temporarily. Before descending into a left subtree, find that subtree's rightmost node — the node an inorder walk would visit immediately before the current one — and point its empty right pointer back at the current node. That borrowed pointer is called a thread, and it is the breadcrumb that lets you climb back without a stack. When the left subtree is exhausted, following the thread returns you to where you started. You then cut the thread, restoring the tree exactly as it was, and continue right. What makes this the preorder variant rather than inorder is one detail: - Visit the node when you lay the thread — on first arrival — instead of when you cut it. Preorder means parent before left subtree, and first arrival is precisely that moment. Moving that single visit between the two branches is the entire difference between Morris preorder and Morris inorder, which is why learning one gives you the other almost free.
Identical threading machinery to Morris inorder, with the visit moved to the first arrival instead of the second. That single line's position is the entire difference between the two traversals — the same observation that distinguishes recursive preorder from inorder.
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 is for
A thread is a temporary right pointer from the rightmost node of a left subtree back to that subtree's root. It replaces the stack frame that a normal traversal would use to remember where to return. Every thread laid must later be cut, or the tree is left corrupted with a cycle.
Handle the no-left-child case
If the current node has no left child, there is nothing to thread. Visit it and move right. This is the simple path, and in a right-skewed tree it is the only one ever taken.
Find the inorder predecessor
When a left child exists, walk to node.left and then right as far as possible. Stop when the right pointer is null (no thread yet) or points back at the current node (a thread you laid earlier). That second condition is what tells the two visits of the same node apart.
First arrival: visit, thread, descend
If the predecessor's right pointer is null, this is your first time here. Visit the node now — this is what makes the traversal preorder — then set the predecessor's right pointer to the current node and move left. The node is emitted before its left subtree, exactly as preorder requires.
Second arrival: cut the thread and go right
If the predecessor's right already points at the current node, the left subtree is finished and you arrived back via your own thread. Set that pointer back to null to repair the tree, and move right without visiting — the node was already emitted on first arrival.
See the one-line difference from inorder
Morris inorder is this identical algorithm with the visit moved into the second-arrival branch, since inorder emits a node after its left subtree. Only the placement of the visit changes; the threading machinery is untouched.
Cost of the traversal
Each edge is traversed at most three times — descending, threading, and returning — so the time is O(n) despite the inner predecessor walks looking like they add a factor. Space is genuinely O(1): no stack, no recursion, only a handful of pointers, with the tree restored to its original shape by the end.
Solution & live demo
Common pitfalls
Visiting on the second arrival
else:
pred.right = None
res.append(cur.val)
cur = cur.rightif not pred.right:
res.append(cur.val)
pred.right = curEmitting when the thread is cut yields inorder. Preorder requires the node before its left subtree, which is the moment the thread is first laid.
Forgetting to visit in the no-left-child branch
if not cur.left:
cur = cur.rightif not cur.left:
res.append(cur.val)
cur = cur.rightA node with no left child is never threaded, so this branch is its only chance to be emitted. Skipping it silently drops every such node from the output.
Leaving threads in place
else:
cur = cur.rightelse:
pred.right = None
cur = cur.rightEven though preorder has already emitted the node by this point, the thread still has to be removed or the tree stays corrupted for every future use. The cut is about restoring the structure, not about output.
Edge cases
Visit and step right — same as inorder here.
Never threads at all; just walks and visits.