GeeksforGeeks Hard

Morris Inorder Traversal

Inorder traversal in O(1) space — no recursion, no stack.

treemorristhreading

02

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.

03

Approach

1

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).

2

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.

3

Tree restored

Every thread is removed on second arrival — the tree ends unchanged, and each edge is walked ≤ 3 times → O(n).

04

Solution & live demo

python

▶1def morris_inorder(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                pred.right = cur      # lay the thread
▶13                cur = cur.left
▶14            else:
▶15                pred.right = None     # cut it, left side done
▶16                res.append(cur.val)
▶17                cur = cur.right
▶18    return res

05

Edge cases

No left child

Visit immediately and go right — the trivial case.

Interrupting mid-traversal

Threads would be left dangling — Morris must run to completion to restore the tree.

06

Complexity

Time

O(n)

Space

O(1)

Threads replace the stack; tree restored at the end.