Binary Tree - Morris InOrder Traversal

Problem Statement

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

The challenge is to perform the traversal:

Without Recursion

Without Stack

O(1) Extra Space

Brute Force Intuition

In an interview, you can explain it like this:

Perform a normal recursive inorder traversal.

This naturally follows:

Left

↓

Root

↓

Right

However, recursion uses the system call stack.

Complexity

• Time Complexity: O(N)
• Space Complexity: O(H)

Better Approach

Use an explicit stack.

Traverse:

Go Left

↓

Visit Node

↓

Go Right

Complexity

• Time Complexity: O(N)
• Space Complexity: O(H)

Moving Towards the Optimal Approach

Can we perform inorder traversal without:

Recursion

OR

Stack?

Yes.

The idea is to temporarily modify the tree.

Instead of returning using recursion,

we create a temporary link from the inorder predecessor back to the current node.

This technique is called:

Threading the Binary Tree

Pattern Recognition

Whenever you see:

• Binary Tree Traversal
• O(1) Extra Space
• No Stack
• No Recursion

Think:

Morris Traversal

Key Observation

For every node:

Case 1

No Left Child

Visit it immediately.

Move:

Right

Case 2

Has Left Child

Find its:

Inorder Predecessor

(the rightmost node of the left subtree)

Now:

If predecessor's right is:

NULL

Create a temporary thread.

Predecessor

↓

Current

Move:

Left

If predecessor already points to current,

remove the thread,

visit current,

move right.

Visualization

Original Tree

        4
       / \
      2   5
     / \
    1   3

Temporary Thread

3
 \
  4

instead of

NULL

Once returned,

remove it again.

Tree becomes unchanged.

Optimal Java Solution

class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> ans = new ArrayList<>();

        TreeNode curr = root;

        while (curr != null) {

            if (curr.left == null) {

                ans.add(curr.val);

                curr = curr.right;

            } else {

                TreeNode pred = curr.left;

                while (pred.right != null &&
                       pred.right != curr) {

                    pred = pred.right;
                }

                if (pred.right == null) {

                    pred.right = curr;

                    curr = curr.left;

                } else {

                    pred.right = null;

                    ans.add(curr.val);

                    curr = curr.right;
                }
            }
        }

        return ans;
    }
}

Dry Run

Tree

        4
       / \
      2   5
     / \
    1   3

Step 1

Current:

4

Left exists.

Find predecessor:

3

Create thread:

3 → 4

Move left.

Step 2

Current:

2

Find predecessor:

1

Create:

1 → 2

Move left.

Step 3

Current:

1

No left.

Visit:

1

Move via thread.

Step 4

Back to:

2

Remove thread.

Visit:

2

Move right.

Step 5

Visit:

3

Return through thread.

Visit:

4

Visit:

5

Final Traversal

1

2

3

4

5

Why Morris Traversal Works?

Instead of remembering parent nodes using recursion,

we temporarily connect:

Inorder Predecessor

↓

Current Node

This allows us to return after completing the left subtree.

Before leaving,

the temporary connection is removed,

so the original tree remains unchanged.

Each edge is traversed at most twice.

Complexity Analysis

Interview One-Liner

Morris Traversal performs inorder traversal in O(1) extra space by temporarily creating threads from each node's inorder predecessor back to the current node.

Pattern Learned

Need O(1) Space

↓

No Stack

↓

No Recursion

↓

Thread Binary Tree

↓

Morris Traversal

Similar Problems

• Morris Inorder Traversal
• Morris Preorder Traversal
• Recover Binary Search Tree
• BST Iterator
• Binary Tree Traversals

Memory Trick

Think:

Has Left Child?

↓

Find Predecessor

↓

Thread Exists?

↓

No

Create Thread

Go Left

----------------

Yes

Remove Thread

Visit Node

Go Right

Mental Model

Current

↓

Left Exists?

↓

Find Rightmost Node

↓

Thread It

↓

Come Back

↓

Remove Thread

↓

Visit

Whenever you hear:

"Traverse a binary tree without recursion or stack"

your brain should immediately think:

Morris Traversal (Threaded Binary Tree)