Morris Preorder Traversal
Preorder traversal in O(1) space using Morris threading.
Open on GeeksforGeeks ↗Intuition
Identical threading to Morris inorder with one change: visit the node when laying the thread (first arrival) instead of when cutting it. Preorder visits parents before left subtrees — first arrival is exactly that moment.
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
Same predecessor walk
Find the left subtree's rightmost node; check for an existing thread.
Visit on first arrival
No thread → visit cur NOW, lay the thread, descend left. Thread exists → just cut it and go right (already visited).
One-line difference
Moving one append between the two branches converts inorder ↔ preorder — worth internalizing.
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.