What is Morris Traversal?
Learn how Morris traversal visits a binary tree in order using O(1) extra space via temporary threading, with a full interview answer.
Expected Interview Answer
Morris traversal is a technique for performing in-order (or pre-order) traversal of a binary tree in O(1) extra space by temporarily converting the tree into a threaded structure, avoiding both the recursion stack and an explicit stack that standard traversals need.
For each node, the algorithm finds its in-order predecessor (the rightmost node in its left subtree) and creates a temporary link from that predecessor back to the current node, then moves left. When traversal later returns to the current node via that temporary link, the algorithm visits the node, removes the temporary link to restore the tree to its original shape, and moves right. If a node has no left child, it is visited immediately and traversal moves right directly. Because every temporary link is created once and removed once, the algorithm still runs in O(n) time overall despite revisiting some nodes, but it needs zero extra memory beyond a couple of pointers — a significant improvement over the O(h) stack space (h = tree height) that recursive or stack-based traversal requires. This makes it valuable in memory-constrained environments or when traversing extremely deep or unbalanced trees where recursion could risk a stack overflow.
- O(1) extra space, no recursion stack or explicit stack
- Still O(n) overall time despite temporary re-visits
- Avoids stack-overflow risk on very deep or skewed trees
- Leaves the tree in its original shape once traversal completes
AI Mentor Explanation
Morris traversal is like a groundskeeper walking a sprawling training facility without carrying a notepad to remember which paths still need checking. Before heading down a side path, the groundskeeper leaves a chalk mark pointing back to where they came from, so when the side path dead-ends, they can follow the chalk mark straight back instead of relying on memory. Once back, the chalk mark is erased immediately, leaving no trace, and the groundskeeper continues past that junction. This chalk-and-erase trick means the facility can be fully checked without ever carrying a running list of unvisited spots.
Step-by-Step Explanation
Step 1
Check for a left child
If the current node has no left child, visit it and move to its right child.
Step 2
Find the in-order predecessor
Otherwise, walk right within the left subtree to find the current node's predecessor.
Step 3
Create or follow the thread
If the predecessor's right pointer is null, thread it to the current node and move left; if it already points back, remove the thread, visit the node, and move right.
Step 4
Repeat until the current pointer is null
Every temporary thread is created once and removed once, so total work stays O(n) despite the extra passes.
What Interviewer Expects
- Explain the temporary threading via the in-order predecessor
- State O(1) extra space vs O(h) for recursive/stack-based traversal
- Confirm overall time remains O(n) despite revisiting nodes
- Note that the tree is fully restored to its original shape after traversal
Common Mistakes
- Forgetting to remove the temporary thread, leaving the tree permanently modified
- Confusing Morris traversal's predecessor-threading with simple parent pointers
- Assuming it changes the time complexity to something better than O(n) (it does not — it only improves space)
- Not handling the case where a node has no left child
Best Answer (HR Friendly)
“Morris traversal is a clever way to walk a binary tree in order without using any extra stack or recursion. It temporarily borrows unused pointers in the tree itself to remember where to come back to, then cleans those pointers up as it goes, so the tree ends up looking exactly like it did before, and I only ever use a constant amount of extra memory.”
Code Example
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def morris_inorder(root):
result = []
current = root
while current:
if current.left is None:
result.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right is not current:
predecessor = predecessor.right
if predecessor.right is None:
predecessor.right = current # thread it
current = current.left
else:
predecessor.right = None # remove thread, restore tree
result.append(current.val)
current = current.right
return resultFollow-up Questions
- How would you modify Morris traversal to produce pre-order instead of in-order?
- Why does the total time complexity remain O(n) despite some nodes being visited twice?
- What real risk does recursive traversal have on very deep trees that Morris traversal avoids?
- How would you verify the tree is correctly restored after a Morris traversal?
MCQ Practice
1. What is Morris traversal's key advantage over recursive or stack-based in-order traversal?
Morris traversal threads the tree temporarily instead of using a call stack or explicit stack, giving O(1) extra space.
2. What does Morris traversal use to remember where to return after visiting a node's left subtree?
It links the rightmost node of the left subtree (the predecessor) back to the current node, then removes that link once used.
3. What is the overall time complexity of Morris traversal on a tree with n nodes?
Each temporary thread is created once and removed once, so total work across all nodes remains O(n) despite the extra visits.
Flash Cards
What space complexity does Morris traversal achieve? — O(1) extra space, avoiding recursion or an explicit stack.
What does Morris traversal thread to the current node? — The in-order predecessor's right pointer, temporarily.
What happens to the tree after a Morris traversal completes? — It is fully restored to its original shape, with all temporary threads removed.
What is Morris traversal's overall time complexity? — O(n), the same as standard traversal, despite some nodes being visited twice.