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

Morris Preorder Traversal

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

Root → Left Subtree → Right Subtree

The recursive method uses the call stack to remember where traversal must return after completing a subtree. The iterative method stores pending nodes in an explicit stack.

Both methods require additional space proportional to the tree’s height:

O(H)

Morris Preorder Traversal generates the same preorder sequence without recursion and without an explicit stack. It temporarily connects a node’s inorder predecessor to the current node, creating a return path from the left subtree.

Every temporary connection is removed after use, so the original tree is restored before the traversal finishes.

The main advantage is:

Auxiliary Space Complexity: O(1)

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

The traversal must:

• Visit every node in preorder.

• Avoid recursion.

• Avoid using an explicit stack.

• Use constant auxiliary space.

• Remove every temporary connection before finishing.

Example

Consider a 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.

Preorder visits:

Root → Left → Right

Therefore, the traversal is:

1 → 2 → 4 → 3

Answer = [1, 2, 4, 3]

Why Do Normal Traversals Need Extra Space?

In recursive preorder traversal, the current node is visited before entering its subtrees.

When recursion moves into the left subtree, the call stack remembers:

• The current node

• Its unprocessed right subtree

• Where traversal must return after finishing the left subtree

The iterative method stores the same pending information in an explicit stack.

Morris traversal temporarily stores this return information inside an unused right pointer of the tree.

It creates a temporary link from the final node of the left subtree back to the current node. This temporary connection is called a thread.

Core Idea of Morris Preorder Traversal

Suppose the current node has a left subtree.

The rightmost node in that left subtree is the current node’s inorder predecessor.

For a current node C:

Predecessor = Rightmost node in C's left subtree

The predecessor is important because it is the final node reached before traversal must return from the left subtree to the current node.

Morris traversal temporarily changes:

predecessor.right = current

This creates a return path.

However, preorder requires the root to be visited before its left subtree. Therefore, the current node is added to the answer before creating the thread and moving left.

After the left subtree is processed, traversal returns through the thread. The thread is removed, and traversal moves to the current node’s right subtree.

Finding the Predecessor

For the example tree, let:

current = 1

Node 1 has a left child, so predecessor searching begins from node 2.

Node 2 has a right child 4, so move right.

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

Therefore:

Predecessor of 1 = 4

Since 4.right is initially NULL, Morris traversal creates:

4.right = 1

Before creating this thread, node 1 is added to the preorder answer.

Traversal then moves to:

current = 2

Two Main Cases

A pointer named current represents the node 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.

Visit the current node immediately:

answer.add(current)

Then move through its right pointer:

current = current.right

The right pointer may be:

• A normal right child, or

• A temporary thread leading back to an ancestor

Current Node Has a Left Child

Find the rightmost node in the current node’s left subtree.

Let this node be predecessor.

Stop predecessor searching when:

• predecessor.right is NULL, or

• predecessor.right points to current

These two conditions distinguish the first and second encounters with the current node.

First Encounter with a Node

If:

predecessor.right = NULL

the left subtree has not been processed.

Since preorder visits the root before its subtrees:

• Visit the current node.

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

• Move into the left subtree.

The operations are:

Visit current

predecessor.right = current

current = current.left

Second Encounter with a Node

If:

predecessor.right = current

the temporary thread already exists.

This means traversal has completed the current node’s left subtree and returned through the thread.

During this encounter:

• Do not visit the current node again.

• Remove the temporary thread.

• Move into the right subtree.

The operations are:

predecessor.right = NULL

current = current.right

The node is not added to the answer because it was already visited during its first encounter.

Mental Model

For a node with a left subtree:

First Encounter

• Visit the node.

• Find its predecessor.

• Create the temporary thread.

• Move into the left subtree.

Second Encounter

• Find the same predecessor.

• Detect the existing thread.

• Remove the thread.

• Move into the right subtree.

• Do not visit the node again.

For a node without a left subtree:

• Visit the node immediately.

• Move through its right pointer.

The complete rule is:

• No left child: Visit and move right.

• Left child with no thread: Visit, create the thread, and move left.

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

Morris Inorder and Morris Preorder

Both traversals use the same predecessor and threading mechanism. The only major difference is when the current node is visited.

In Morris inorder, the root must wait until the complete left subtree is processed.

In Morris preorder, the root must be visited before entering the left subtree.

Algorithm

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

• If current has no left child, visit it and move through its right pointer.

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

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

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

• Repeat until current becomes NULL, ensuring every created thread has been removed.

Complete Dry Run

Consider the following tree:

• Root is 1.

• Left child of 1 is 2.

• Right child of 1 is 3.

• Right child of 2 is 4.

Initial state:

current = 1

answer = []

Step 1: Start at Node 1

Node 1 has a left child.

The search for its inorder predecessor begins from:

predecessor = 2

Step 2: Move to the Rightmost Node

Node 2 has a right child 4.

Move:

predecessor = 4

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

Step 3: Visit Node 1

The right pointer of predecessor 4 is NULL, so this is the first encounter with node 1.

Preorder visits the root before its left subtree. Therefore, node 1 is added:

answer = [1]

Step 4: Create the Thread

Create:

4.right = 1

This temporary thread will return the traversal to node 1 after its left subtree has been completed.

Move left:

current = 2

Step 5: Process Node 2

Node 2 has no left child.

Visit it:

answer = [1, 2]

Move through its normal right pointer:

current = 4

Step 6: Process Node 4

Node 4 has no left child.

Visit it:

answer = [1, 2, 4]

Its right pointer is the temporary thread to node 1.

Follow the thread:

current = 1

Step 7: Return to Node 1

Node 1 has a left child, so predecessor searching begins again:

predecessor = 2

Move right from node 2 to node 4.

Now:

4.right = 1

The predecessor already points to the current node. Therefore, the left subtree of node 1 has been completely processed.

Step 8: Remove the Thread

Restore the original pointer:

4.right = NULL

Node 1 is not visited again because it was already added during its first encounter.

Move into the right subtree:

current = 3

Step 9: Process Node 3

Node 3 has no left child.

Visit it:

answer = [1, 2, 4, 3]

Move to its right pointer:

current = NULL

Step 10: Finish the Traversal

Since current is NULL, the traversal stops.

The final preorder traversal is:

[1, 2, 4, 3]

The temporary thread has been removed, so the original tree is restored.

Why Does Morris Preorder Work?

Morris Preorder preserves the Root → Left → Right order through two observations.

The Root Must Be Visited During the First Encounter

When a node with a left subtree is encountered for the first time, neither subtree has been processed.

Since preorder requires the root first, the node is visited before traversal moves left.

The Thread Returns Traversal After the Left Subtree

The predecessor is the final node reached before leaving the current node’s left subtree.

Its temporary thread leads traversal back to the current node.

When the thread is found:

• The left subtree is complete.

• The current node has already been visited.

• The thread is removed.

• Traversal moves into the right subtree.

This produces:

Current Node → Complete Left Subtree → Complete Right Subtree

which is exactly preorder.

Why Is a Node Not Visited During the Second Encounter?

A node with a left subtree is encountered twice:

• Once before entering the left subtree

• Once after returning through the thread

Preorder requires the node to appear only once and before its descendants.

Therefore, the node is added during the first encounter.

The second encounter exists only to:

• Detect completion of the left subtree

• Remove the temporary thread

• Continue into the right subtree

Adding the node during both encounters would produce duplicate values in the answer.

Why Does the Traversal Not Enter an Infinite Loop?

The temporary thread creates a link from the predecessor back to the current node.

While searching for the predecessor, traversal must stop when:

• The right pointer is NULL, or

• The right pointer points to current

The second condition detects an existing thread.

Without it, predecessor searching could repeatedly follow the temporary connection and create a cycle.

Complexity Analysis

Each node is processed a constant number of times.

Although predecessor searching occurs inside the main traversal loop, each relevant edge is followed only a limited number of times:

• While locating a predecessor to create a thread

• While returning through a thread

• While locating the same predecessor to remove the thread

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

Time Complexity: O(N)

Morris Preorder maintains only a constant number of pointers, mainly:

• current

• predecessor

It does not use recursion, a stack, a queue, or a parent mapping.

Auxiliary Space Complexity: O(1)

The traversal result requires O(N) output space, which is excluded from auxiliary-space analysis.

Does Morris Preorder Modify the Tree?

Yes, but only temporarily.

For every required return path, Morris traversal changes:

predecessor.right = NULL

into:

predecessor.right = current

After the left subtree is complete, the pointer is restored:

predecessor.right = NULL

The complete lifecycle is:

NULL → Temporary Thread → NULL

If traversal finishes normally, the tree’s final structure remains unchanged.

Important Limitation

Morris traversal temporarily modifies the tree while it is running.

It may be unsuitable when:

• The tree is immutable.

• Multiple operations access the tree concurrently.

• The traversal may stop unexpectedly.

• An exception can occur after creating a thread.

• An early return can leave threads behind.

• Tree nodes are shared with another data structure.

Recursive or stack-based traversal may be safer when temporary structural changes are not allowed.

Comparison with Other Preorder Methods

For a balanced tree:

H = O(log N)

For a completely skewed tree:

H = O(N)

Morris traversal maintains O(1) auxiliary space in both cases.

Important Edge Cases

Empty Tree

If the root is NULL, traversal never begins.

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 and traversal moves right. No temporary threads are required.

Completely Left-Skewed Tree

Every non-leaf node requires a temporary thread.

Each node is visited before moving left. Traversal later follows and removes the threads while returning upward.

Duplicate Values

Morris traversal uses node pointers and structure rather than comparing node values.

Duplicate values do not affect its correctness.

Invalid Tree with a Cycle

Morris traversal assumes that the input is a valid binary tree. Existing cycles or unexpected pointer connections can prevent correct predecessor detection.

Applications

Morris Preorder is useful when:

• Preorder traversal must use constant auxiliary space.

• Recursion is prohibited.

• An explicit stack is not allowed.

• The tree may be deep enough to cause stack overflow.

• Memory is highly constrained.

• An interview asks for traversal without recursion or stack.

• A tree must be processed before its subtrees using constant space.

Common Mistakes

• Using the Morris Inorder visit timing for preorder.

• Waiting until thread removal before visiting the current node.

• Visiting the current node during both encounters.

• Forgetting to visit a node that has no left child.

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

• Searching past a predecessor whose right pointer already equals current.

• Creating a thread before recording the current node.

• Forgetting to move into the left subtree after creating a thread.

• Forgetting to remove the thread during the second encounter.

• Adding the current node again when removing its thread.

• Treating a temporary thread as an original right child.

• Assuming the nested predecessor search produces O(N²) time.

• Returning early and leaving the tree modified.

• Counting the output list as constant auxiliary space.

• Using Morris traversal when temporary tree modification is prohibited.

FAQs

Q1. What is the main difference between Morris Inorder and Morris Preorder?

Both use the same predecessor and thread mechanism. Morris Inorder visits a node during its second encounter after removing the thread, while Morris Preorder visits it during the first encounter before creating the thread.

Q2. Why is the current node visited before creating the thread?

Preorder requires the root to appear before its left subtree. Creating the thread indicates that traversal is about to enter the left subtree, so the root must be recorded first.

Q3. Why is the current node not visited when the thread is removed?

The node was already visited during its first encounter. The second encounter is only used to remove the temporary thread and move into the right subtree.

Q4. How is Morris Preorder still O(N) with an inner predecessor search?

Each edge is followed only a constant number of times while creating, following, and removing threads. Therefore, all predecessor searches together take O(N) time.

Q5. Does Morris Preorder permanently change the binary tree?

No, provided traversal completes correctly. Every temporary thread is removed during the second encounter, restoring the original tree.

Q6. When should Morris Preorder be avoided?

Avoid it when the tree is immutable, shared concurrently, or traversal may terminate before cleanup. In those situations, recursion or an explicit stack is safer.