Morris Traversal
An interactive, step-by-step visualisation of Morris Traversal.
- Category
- Trees
- Time complexity
- O(n)
- Space complexity
- O(1)
Pseudocode
no left child: visit, go right else: find inorder predecessor no thread: create thread, go left thread exists: remove it, visit, go right
Reference implementation
# O(1) space inorder via temporary threads
while cur:
if not cur.l:
visit(cur); cur = cur.r
else:
pred = rightmost(cur.l)
if not pred.r:
pred.r = cur; cur = cur.l
else:
pred.r = None; visit(cur); cur = cur.r