Morris Preorder Traversal
Preorder traversal in O(1) space using Morris threading.
Open on GeeksforGeeks ↗02
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.
03
Approach
1
Same predecessor walk
Find the left subtree's rightmost node; check for an existing thread.
2
Visit on first arrival
No thread → visit cur NOW, lay the thread, descend left. Thread exists → just cut it and go right (already visited).
3
One-line difference
Moving one append between the two branches converts inorder ↔ preorder — worth internalizing.
04
Solution & live demo
python
▶1def morris_preorder(root):
▶2 res, cur = [], root
▶3 while cur:
▶4 if not cur.left:
▶5 res.append(cur.val)
▶6 cur = cur.right
▶7 else:
▶8 pred = cur.left
▶9 while pred.right and pred.right is not cur:
▶10 pred = pred.right
▶11 if not pred.right:
▶12 res.append(cur.val) # visit on FIRST arrival
▶13 pred.right = cur
▶14 cur = cur.left
▶15 else:
▶16 pred.right = None
▶17 cur = cur.right
▶18 return res
05
Edge cases
No left child
Visit and step right — same as inorder here.
Right-only chain
Never threads at all; just walks and visits.
06
Complexity
Time
O(n)
Space
O(1)
Same edge bound as Morris inorder.