모리스 사전 주문 트래버설

Problem Statement

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

The challenge is to perform the traversal:

Without Recursion

Without Stack

O(1) Extra Space

Enter fullscreen mode Exit fullscreen mode

Brute Force Intuition

In an interview, you can explain it like this:

Perform a normal recursive preorder traversal.

Traversal order:

Root

↓

Left

↓

Right

Enter fullscreen mode Exit fullscreen mode

Recursion naturally remembers the parent nodes.

Complexity

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

Better Approach

Use an explicit stack.

Visit:

Root

↓

Left

↓

Right

Enter fullscreen mode Exit fullscreen mode

Complexity

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

Moving Towards the Optimal Approach

Can we perform preorder traversal without:

Recursion

OR

Stack?

Enter fullscreen mode Exit fullscreen mode

Yes.

Instead of using recursion,

temporarily connect the inorder predecessor back to the current node.

This temporary connection is called a:

Thread

Enter fullscreen mode Exit fullscreen mode

Unlike Morris Inorder,

here we visit the node before moving to the left subtree.

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

Enter fullscreen mode Exit fullscreen mode

Visit it immediately.

Move:

Right

Enter fullscreen mode Exit fullscreen mode

Case 2

Has Left Child

Enter fullscreen mode Exit fullscreen mode

Find its:

Inorder Predecessor

Enter fullscreen mode Exit fullscreen mode

(the rightmost node of the left subtree)

If predecessor’s right is:

NULL

Enter fullscreen mode Exit fullscreen mode

Visit current node.

Create a temporary thread.

Predecessor

↓

Current

Enter fullscreen mode Exit fullscreen mode

Move:

Left

Enter fullscreen mode Exit fullscreen mode

If predecessor already points to current,

remove the thread,

move to the right subtree.

Notice:

Unlike Morris Inorder,

we do not visit the node while removing the thread.

Visualization

Original Tree

        4
       / \
      2   5
     / \
    1   3

Enter fullscreen mode Exit fullscreen mode

Temporary Thread

3
 \
  4

Enter fullscreen mode Exit fullscreen mode

After returning,

the thread is removed,

restoring the original tree.

Optimal Java Solution

class Solution {

    public List<Integer> preorderTraversal(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) {

                    ans.add(curr.val);

                    pred.right = curr;

                    curr = curr.left;

                } else {

                    pred.right = null;

                    curr = curr.right;
                }
            }
        }

        return ans;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Tree

        4
       / \
      2   5
     / \
    1   3

Enter fullscreen mode Exit fullscreen mode

Step 1

Current:

4

Enter fullscreen mode Exit fullscreen mode

Visit:

4

Enter fullscreen mode Exit fullscreen mode

Create thread:

3 → 4

Enter fullscreen mode Exit fullscreen mode

Move left.

Step 2

Current:

2

Enter fullscreen mode Exit fullscreen mode

Visit:

2

Enter fullscreen mode Exit fullscreen mode

Create thread:

1 → 2

Enter fullscreen mode Exit fullscreen mode

Move left.

Step 3

Current:

1

Enter fullscreen mode Exit fullscreen mode

No left child.

Visit:

1

Enter fullscreen mode Exit fullscreen mode

Move through thread.

Step 4

Back to:

2

Enter fullscreen mode Exit fullscreen mode

Remove thread.

Move right.

Visit:

3

Enter fullscreen mode Exit fullscreen mode

Return through thread.

Visit:

5

Enter fullscreen mode Exit fullscreen mode

Final Traversal

4

2

1

3

5

Enter fullscreen mode Exit fullscreen mode

Why Morris Preorder Works?

Instead of using recursion,

we temporarily connect:

Inorder Predecessor

↓

Current Node

Enter fullscreen mode Exit fullscreen mode

Since preorder visits the root first,

we process the node when creating the thread.

When we return,

the thread is removed,

and the original tree is restored.

Each edge is traversed at most twice.

Complexity Analysis

Metric Complexity Time Complexity O(N) Space Complexity O(1)

Interview One-Liner

Morris Preorder Traversal visits the node before creating a temporary thread to its inorder predecessor, achieving preorder traversal in O(1) extra space.

Pattern Learned

Need O(1) Space

↓

No Stack

↓

No Recursion

↓

Thread Binary Tree

↓

Visit Before Going Left

Enter fullscreen mode Exit fullscreen mode

Similar Problems

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

Memory Trick

Think:

Has Left Child?

↓

Find Predecessor

↓

Thread Exists?

↓

No

Visit Node

Create Thread

Go Left

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

Yes

Remove Thread

Go Right

Enter fullscreen mode Exit fullscreen mode

Mental Model

Current

↓

Visit

↓

Thread

↓

Left

↓

Back

↓

Right

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Preorder traversal without recursion or stack”

your brain should immediately think:

Morris Preorder Traversal