Morris Inorder Traversal: Binary Tree Traversal in O(1) Space

Morris Inorder Traversal

Inorder traversal visits the nodes of a binary tree in the following order:

Left Subtree → Root → Right Subtree

The usual recursive method uses the call stack to remember how to return to a node after processing its left subtree. An iterative method replaces the recursion stack with an explicit stack.

Both methods require additional space proportional to the height of the tree:

O(H)

Morris Inorder Traversal performs the same traversal without recursion and without an explicit stack. It temporarily creates links inside the tree so that traversal can return from a node’s left subtree to the node itself.

After using a temporary link, Morris traversal removes it. Therefore, the original tree structure is restored before the traversal finishes.

The major advantage is:

Auxiliary Space Complexity: O(1)

Given the root of a binary tree, return its inorder traversal using Morris traversal.

The traversal must:

• Visit every node in inorder.

• Avoid recursion.

• Avoid using an explicit stack.

• Use only constant auxiliary space.

• Restore every temporary pointer before finishing.

Example

Consider the binary tree with the following relationships:

• Node 1 is the root.

• Node 2 is the left child of 1.

• Node 3 is the right child of 1.

• Node 4 is the right child of 2.

The inorder traversal is:

2 → 4 → 1 → 3

Therefore:

Answer = [2, 4, 1, 3]

Why Do Normal Traversals Need Extra Space?

In recursive inorder traversal, the algorithm first moves toward the leftmost node.

Before moving left, the recursive call stack remembers:

• The current node

• Where traversal must return

• Which right subtree remains unvisited

For example, while processing node 1, recursion moves into its left subtree. After completing that subtree, the stack returns traversal to node 1.

An iterative traversal stores the same pending nodes in an explicit stack.

Morris traversal asks an important question:

Can the tree itself temporarily store the information required to return to a node?

The answer is yes. A currently unused NULL right pointer can temporarily point back to the node that must be visited later.

Core Idea of Morris Traversal

Suppose the current node has a left subtree.

In inorder traversal, the node visited immediately before the current node is the rightmost node in its left subtree.

This node is called the current node’s inorder predecessor.

For a current node C:

Inorder predecessor = Rightmost node in C's left subtree

The predecessor normally has no right child. Morris traversal temporarily changes this NULL pointer so that it points to the current node:

predecessor.right = current

This temporary connection is called a thread.

After the left subtree is completed, traversal reaches the predecessor again. Its temporary right pointer leads back to the current node.

The thread is then removed:

predecessor.right = NULL

Only after removing the thread is the current node visited.

What Is an Inorder Predecessor?

The inorder predecessor of a node is the node that appears immediately before it in inorder traversal.

When a node has a left subtree, its predecessor is the rightmost node in that left subtree.

For node 1 in the example tree:

• Move to its left child 2.

• Continue right from 2.

• Reach node 4.

• Node 4 is the rightmost node in the left subtree of 1.

Therefore:

Inorder predecessor of 1 = 4

Morris traversal temporarily creates:

4.right = 1

This thread provides a path back to node 1 after nodes 2 and 4 have been processed.

Two Main Cases

During Morris traversal, a pointer named current represents the node currently being processed.

There are two main cases.

Current Node Has No Left Child

If current.left is NULL, there is no left subtree to process.

According to inorder order, the current node can be visited immediately.

After visiting it:

current = current.right

The right pointer may represent:

• A normal right child, or

• A temporary thread leading back to an ancestor

Current Node Has a Left Child

If a left child exists, find the rightmost node in the left subtree.

Let this node be predecessor.

Two situations are possible.

The Predecessor’s Right Pointer Is NULL

This is the first time the current node is encountered.

The left subtree has not yet been processed.

Create a temporary thread:

predecessor.right = current

Then move into the left subtree:

current = current.left

The current node is not visited yet because inorder requires its left subtree to be completed first.

The Predecessor’s Right Pointer Points to Current

This is the second time the current node is encountered.

The existing thread proves that the complete left subtree has already been processed.

Remove the thread:

predecessor.right = NULL

Now visit the current node and move to its right subtree:

current = current.right

Mental Model

Every node with a left subtree is encountered twice.

First Encounter

• Find its inorder predecessor.

• Create a thread from the predecessor to the current node.

• Move into the left subtree.

• Do not visit the current node yet.

Second Encounter

• Find the same predecessor again.

• Detect the existing thread.

• Remove the thread.

• Visit the current node.

• Move into the right subtree.

A node without a left child is encountered once and visited immediately.

This gives a simple rule:

• No left child: Visit and move right.

• Left child with no thread: Create the thread and move left.

• Left child with an existing thread: Remove the thread, visit, and move right.

Algorithm

• Initialize current with the root because traversal begins from the complete tree.

• If current has no left child, visit it and move to its right pointer because no left subtree is pending.

• Otherwise, find the rightmost node in the left subtree, stopping when its right pointer is either NULL or points to current.

• If the predecessor’s right pointer is NULL, create a temporary thread to current and move to the left child.

• If the predecessor already points to current, remove the thread, visit current, and move to its right child.

• Repeat until current becomes NULL, which means every node has been processed and every created thread has been removed.

Complete Dry Run

Why Does Morris Traversal Work?

Morris traversal preserves the required inorder sequence through two observations.

A Node Without a Left Subtree Can Be Visited Immediately

If no left subtree exists, there is nothing that must be processed before the current node.

Therefore, visiting the node and moving right follows inorder order.

A Node With a Left Subtree Must Be Visited After That Subtree

The inorder predecessor is the final node visited in the current node’s left subtree.

Creating a thread from the predecessor to the current node ensures that traversal returns immediately after completing the left subtree.

When the thread is encountered:

• The left subtree is complete.

• The thread is removed.

• The current node is visited.

• Traversal continues into the right subtree.

Therefore, every node is visited only after its complete left subtree and before its right subtree.

Why Does the Traversal Not Enter an Infinite Loop?

A temporary thread points from the predecessor back to the current node.

Without a special check, predecessor searching could repeatedly follow this thread and create a cycle.

Therefore, the predecessor search must stop when its right pointer is:

• NULL, meaning no thread exists, or

• Equal to current, meaning the previously created thread has been found

The second condition allows the traversal to detect the return from the left subtree, remove the thread, and continue forward.

Why Is the Time Complexity O(N)?

Morris traversal contains a search for the predecessor inside its main loop. This may initially appear to produce O(N²) time.

However, each relevant edge is followed only a constant number of times:

• Once while moving down or right during traversal

• Once while finding a predecessor to create a thread

• Once again while finding the same predecessor to remove the thread

No edge is searched an unlimited number of times.

Therefore, the total number of pointer movements remains proportional to the number of nodes.

Time Complexity: O(N)

Why Is the Auxiliary Space O(1)?

Morris traversal does not use:

• A recursion stack

• An explicit stack

• A queue

• A parent mapping

• A visited set

It maintains only a constant number of pointers, mainly:

• current

• predecessor

Therefore:

Auxiliary Space Complexity: O(1)

The list containing the traversal result requires O(N) output space, but output space is generally excluded from auxiliary-space analysis.

Does Morris Traversal Modify the Tree?

Yes, but only temporarily.

Whenever the current node has an unprocessed left subtree, Morris traversal changes the predecessor’s NULL right pointer into a thread.

After the left subtree has been processed, the same thread is detected and removed.

The expected state transition is:

NULL → Temporary Thread → NULL

If the algorithm completes correctly, every changed pointer returns to its original value.

Therefore, the tree’s final structure remains unchanged.

Important Limitation of Temporary Modification

Although Morris traversal restores the tree, it modifies the structure while traversal is running.

This can be unsafe when:

• The tree is immutable.

• Multiple threads are reading or modifying the same tree.

• Another operation traverses the tree simultaneously.

• Traversal may stop unexpectedly before cleanup.

• An exception or early return occurs after creating a thread.

• Tree nodes are shared by another data structure.

In such situations, recursive or stack-based traversal may be safer despite using additional memory.

Comparison with Other Inorder Methods

For a balanced tree:

H = O(log N)

For a completely skewed tree:

H = O(N)

Morris traversal maintains constant auxiliary space in both cases.

Important Edge Cases

Empty Tree

If the root is NULL, current is also NULL.

The traversal loop never begins, so the result is empty.

Answer = []

Single Node

The root has no left child, so it is visited immediately.

Answer = [root]

Completely Right-Skewed Tree

Every node has no left child.

Each node is visited immediately, and no temporary threads are created.

Completely Left-Skewed Tree

Every non-leaf node requires a temporary thread.

Traversal first reaches the deepest left node and then follows the threads upward while removing them one by one.

Duplicate Values

Morris traversal depends on node pointers and tree structure, not comparisons between node values.

Duplicate values do not affect the traversal logic.

Existing Modified Pointers

Morris traversal assumes the input is a valid tree. If the structure already contains cycles or unexpected threads, predecessor searching may behave incorrectly.

Applications

Morris traversal is useful when:

• Constant auxiliary space is required.

• Recursion is not allowed.

• The tree may be very deep.

• Stack overflow must be avoided.

• Traversal is required in a memory-constrained environment.

• An interview asks for inorder traversal without stack or recursion.

• The same threading concept is extended to Morris preorder or postorder traversal.

Common Mistakes

• Visiting the current node before processing its left subtree.

• Selecting the left child directly as the predecessor without moving to the rightmost node.

• Searching for the predecessor without stopping when its right pointer equals current.

• Creating a thread but forgetting to move current to its left child.

• Visiting the current node when creating the thread.

• Forgetting to remove the temporary thread during the second encounter.

• Moving right before visiting the current node after thread removal.

• Treating a temporary thread as a normal right child.

• Assuming the nested predecessor search makes the total complexity O(N²).

• Counting the result list as constant auxiliary space.

• Using Morris traversal on an immutable tree.

• Returning early and leaving temporary threads inside the tree.

• Assuming duplicate values prevent Morris traversal from working.

• Forgetting to verify that the original tree is restored after traversal.

FAQs

Q1. Why is the current node not visited when a thread is created?

Creating a thread occurs during the first encounter with a node. Its left subtree has not been processed yet, so visiting it would violate the inorder order. The node is visited during the second encounter after the thread is found and removed.

Q2. Why is the rightmost node of the left subtree used?

The rightmost node is the final node visited in the left subtree during inorder traversal. Connecting it to the current node creates the correct return path after the entire left subtree is complete.

Q3. How can Morris traversal be O(N) when it repeatedly searches for predecessors?

Each tree edge is followed only a constant number of times while creating and removing threads. Across the complete traversal, these searches total O(N) pointer movements.

Q4. Does Morris traversal permanently change the tree?

No, if the traversal completes correctly. Every temporary thread is removed during the second encounter with its associated node, restoring the original structure.

Q5. What happens if Morris traversal stops before all threads are removed?

The tree may remain temporarily modified and can contain unexpected cycles. Implementations that may throw exceptions or return early must ensure that all created threads are cleaned up.

Q6. Can the Morris technique be used for other traversals?

Yes. Morris preorder uses a similar threading idea but visits nodes at a different time. Morris postorder is also possible, although it requires more complex edge-reversal operations.