Morris Traversal Algorithm

1. One-Liner

Morris Traversal performs an inorder traversal of a binary tree using O(1) extra space — no stack, no recursion — by temporarily creating "threads" (links) in the tree.

2. The Problem It Solves

Standard inorder traversal of a binary tree uses:

Recursion: O(h) space on the call stack, where h = height of tree. For a skewed tree, h = n.

Iterative with stack: O(h) explicit stack space.

In embedded systems, real-time systems, or memory-constrained environments, even O(h) extra space can be too much. Morris Traversal solves this by achieving O(1) auxiliary space while still visiting every node in inorder.

3. The Core Idea

Imagine you're walking through a forest of tree nodes. Normally, you'd drop breadcrumbs (push to stack) to find your way back. Morris's insight:

Instead of breadcrumbs, create temporary "shortcuts" (threads) in the tree itself.

For each node with a left child:

1. Find the inorder predecessor (rightmost node in the left subtree).

2. If the predecessor's right pointer is null, create a thread (set it to point back to the current node), then go left.

3. If the predecessor already points back to us (thread exists), we've finished the left subtree. Remove the thread, visit the node, and go right.

The tree is temporarily modified but fully restored by the end.

4. How It Works (Step-by-Step)

Step	What Happens
1. Initialize	Set `current = root`, create empty result list
2. Check current	While `current != null`, continue the loop
3. No left child?	Visit `current`, move to `current.right`
4. Has left child	Find inorder predecessor (rightmost in left subtree)
5a. No thread yet	Create thread: `predecessor.right = current`. Move left.
5b. Thread exists	Left subtree done. Remove thread. Visit `current`. Move right.
6. Repeat	Continue until `current` is null

Key insight: Each edge in the tree is traversed at most 3 times (once going down, at most twice for predecessor finding). Total time is O(n), and we only use O(1) extra space (just a few pointers).

5. Dry Run Example

Tree:

Step	Current	Action	Thread	Result So Far
1	4	Has left. Pred=3. No thread. Create 3→4. Go left.	3→4	[]
2	2	Has left. Pred=1. No thread. Create 1→2. Go left.	1→2, 3→4	[]
3	1	No left. Visit 1. Move right (thread → 2).	1→2, 3→4	[1]
4	2	Has left. Pred=1. Thread exists (1→2). Remove. Visit 2. Move right.	3→4	[1, 2]
5	3	No left. Visit 3. Move right (thread → 4).	3→4	[1, 2, 3]
6	4	Has left. Pred=3. Thread exists (3→4). Remove. Visit 4. Move right.	—	[1, 2, 3, 4]
7	6	Has left. Pred=5. No thread. Create 5→6. Go left.	5→6	[1, 2, 3, 4]
8	5	No left. Visit 5. Move right (thread → 6).	5→6	[1, 2, 3, 4, 5]
9	6	Has left. Pred=5. Thread exists. Remove. Visit 6. Move right.	—	[1, 2, 3, 4, 5, 6]
10	7	No left. Visit 7. Move right (null). Done!	—	[1, 2, 3, 4, 5, 6, 7]

Final result: [1, 2, 3, 4, 5, 6, 7] — perfect inorder!

6. Key Properties

Property	Value
Extra space	O(1) — only a few pointers
Time complexity	O(n) — each edge traversed ≤ 3 times
Modifies tree?	Temporarily yes, but fully restored
Works for	Inorder, can be adapted for preorder
Thread safety	Not thread-safe (modifies tree structure)
Predecessor found in	O(h) per node, but amortized O(n) total

7. Where It Is Used

Use Case	Why Morris Traversal
Embedded systems	Cannot afford O(h) stack space
Database B-trees	Constant-space tree scanning
Real-time systems	Predictable memory usage
Competitive programming	Asked in hard interview problems
BST validation	Inorder should be sorted — Morris + O(1) check
Kth smallest in BST	Morris + counter to find kth element

8. Interview Tips

What interviewers want to hear:

1. You understand why O(1) space matters (stack overflow risk, memory-constrained systems)

2. You can explain the threading concept (temporary right pointers to create "breadcrumbs")

3. You know the tree is fully restored after traversal (no permanent modification)

4. You can trace through a dry run step by step

5. You understand it's O(n) time despite the nested loops (amortized analysis)

Common follow-up questions:

"Why is it O(n) time despite the inner while loop?" → Each edge is traversed at most 2 times for predecessor finding. Total work across all nodes is O(n).

"Can you do preorder with Morris?" → Yes! Visit the node when creating the thread (before going left) instead of when removing it.

"What's the downside?" → Temporarily modifies the tree. Not safe in concurrent/multi-threaded environments. Cannot be used on immutable trees.

"How do you find the inorder predecessor?" → Go to left child, then keep going right until you hit null or the current node.

"Can you do postorder with Morris?" → Possible but complex. Usually not asked in interviews.

9. Comparison with Other Traversal Methods

Method	Space	Time	Modifies Tree?	Best For
Recursive	O(h)	O(n)	No	Simple implementation
Iterative (Stack)	O(h)	O(n)	No	When recursion depth is a concern
Morris Traversal	O(1)	O(n)	Temporarily	Memory-constrained systems
Parent Pointer	O(1)	O(n)	Needs extra field	If tree nodes have parent pointers

10. Complexity

Metric	Value
Time Complexity	O(n) — every node visited exactly once
Space Complexity	O(1) auxiliary — only pointer variables
Predecessor Search	O(n) total amortized across all nodes
Tree Restoration	100% — all temporary threads removed

Implementation Example (PYTHON)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def morris_inorder(root):
    result = []
    current = root

    while current is not None:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while (predecessor.right and
                   predecessor.right != current):
                predecessor = predecessor.right

            if predecessor.right is None:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                result.append(current.val)
                current = current.right

    return result