Morris Traversal Inorder Without Stack in DSA Java

Mental Model

We visit nodes in order without using extra memory by temporarily changing tree links to remember where to return.

Analogy: Imagine walking through a maze and leaving temporary signs on walls to find your way back without carrying a map or notes.

    4
   / \
  2   5
 / \
1   3

No extra stack or recursion, just clever link changes.

Dry Run Walkthrough

Input: Binary tree: 4 / \ 2 5 / \ 1 3 Perform inorder traversal using Morris Traversal

Goal: Print nodes in inorder sequence: 1 2 3 4 5 without using stack or recursion

Step 1: Start at root (4), find left child (2), find rightmost node in left subtree (3)

4 -> [curr]
2
/ \
1   3 -> right points to null

Why: We need to find where to return after finishing left subtree

Step 2: Make 3's right point to 4 (thread), move curr to left child 2

4
/ \
2 -> [curr]
/ \
1   3 -> right -> 4 (thread)

Why: Thread helps us return to 4 after left subtree

Step 3: At 2, find left child (1), rightmost in left subtree is 1 (no right child)

4
/ \
2 -> [curr]
/ \
1 -> right -> null
3 -> right -> 4 (thread)

Why: Find thread point to return after left subtree of 2

Step 4: Make 1's right point to 2 (thread), move curr to left child 1

4
/ \
2
/ \
1 -> [curr], right -> 2 (thread)
3 -> right -> 4 (thread)

Why: Thread helps us return to 2 after left subtree

Step 5: At 1, no left child, print 1, move curr to right (thread to 2)

1 -> printed
curr -> 2 (via thread)

Why: Left subtree done, visit node and move to right

Step 6: At 2, thread from 1 detected, remove thread, print 2, move curr to right child 3

2 -> printed
1's right reset to null
curr -> 3

Why: Restore tree and visit node after left subtree

Step 7: At 3, no left child, print 3, move curr to right (thread to 4)

3 -> printed
curr -> 4 (via thread)

Why: Visit node and move to right

Step 8: At 4, thread from 3 detected, remove thread, print 4, move curr to right child 5

4 -> printed
3's right reset to null
curr -> 5

Why: Restore tree and visit node after left subtree

Step 9: At 5, no left child, print 5, move curr to right null (end)

5 -> printed
curr -> null (end)

Why: Traversal complete

Result:

1 -> 2 -> 3 -> 4 -> 5 -> null

Annotated Code

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int val) { this.val = val; left = right = null; }
}

public class MorrisInorderTraversal {
    public static void morrisInorder(Node root) {
        Node curr = root;
        while (curr != null) {
            if (curr.left == null) {
                System.out.print(curr.val + " ");
                curr = curr.right; // move to right child
            } else {
                Node pred = curr.left;
                while (pred.right != null && pred.right != curr) {
                    pred = pred.right; // find rightmost in left subtree
                }
                if (pred.right == null) {
                    pred.right = curr; // create thread
                    curr = curr.left; // move to left child
                } else {
                    pred.right = null; // remove thread
                    System.out.print(curr.val + " ");
                    curr = curr.right; // move to right child
                }
            }
        }
    }

    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(3);

        morrisInorder(root);
        System.out.print("\n");
    }
}

while (curr != null) {

continue traversal until all nodes visited

if (curr.left == null) {

if no left child, visit node and move right

curr = curr.right; // move to right child

advance to right subtree or next node

Node pred = curr.left;

find predecessor in left subtree

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

find rightmost node in left subtree or existing thread

if (pred.right == null) { pred.right = curr; curr = curr.left; }

create thread and move left

else { pred.right = null; System.out.print(curr.val + " "); curr = curr.right; }

remove thread, visit node, move right

Output

1 2 3 4 5 

Complexity Analysis

Time: O(n) because each edge is visited at most twice during threading and removal

Space: O(1) because no extra stack or recursion is used, only pointers are changed temporarily

vs Alternative: Compared to recursive or stack-based inorder traversal which uses O(h) space, Morris traversal uses constant space by temporarily modifying tree links

Edge Cases

Empty tree (root is null)

No output, traversal ends immediately

DSA Java

while (curr != null) {

Tree with single node

Prints the single node value and ends

DSA Java

if (curr.left == null) {

Tree with no left children (right skewed)

Traversal visits nodes directly without threading

DSA Java

if (curr.left == null) {

When to Use This Pattern

When asked to do inorder traversal without recursion or stack, think of Morris Traversal which uses temporary threads to remember return points.

Common Mistakes

Mistake: Not restoring the tree by removing threads after visiting nodes
Fix: Always set pred.right = null after visiting the node to restore original tree structure

Mistake: Incorrectly finding predecessor leading to infinite loops
Fix: Ensure the loop to find predecessor stops if pred.right == curr (existing thread)

Summary

Performs inorder traversal of a binary tree without using stack or recursion by temporarily modifying pointers.

Use when you want inorder traversal with O(1) extra space and can modify tree temporarily.

The key insight is to create and remove temporary threads to remember where to return after left subtree.

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to the traditional recursive or stack-based methods?

easy

A. It requires the tree to be balanced

B. It is faster than all other traversal methods

C. It only works on binary search trees

D. It uses no extra space for stack or recursion

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal modifies tree links temporarily to avoid using stack or recursion, so it uses O(1) extra space.

2. Step 2: Compare with traditional methods

   Traditional inorder traversal uses recursion or stack which require O(h) space, where h is tree height.

3. Final Answer:

   It uses no extra space for stack or recursion -> Option D

4. Quick Check:

   Space complexity = O(1) [OK]

Hint: Morris uses threaded links to avoid stack [OK]

Common Mistakes:

• Thinking Morris is faster in time complexity
• Assuming it only works on BSTs
• Believing it requires balanced trees

2. Which of the following code snippets correctly creates the temporary thread link in Morris Traversal inorder method?

easy

A. current.right = predecessor;

B. current.left = predecessor;

C. predecessor.right = current;

D. predecessor.left = current;

Solution

1. Step 1: Identify the thread link direction

   In Morris Traversal, the right child of the inorder predecessor is linked to current node to create a thread.

2. Step 2: Match with code snippet

   The correct assignment is predecessor.right = current; to create the temporary link.

3. Final Answer:

   predecessor.right = current; -> Option C

4. Quick Check:

   Thread link = predecessor.right = current [OK]

Hint: Thread link always sets predecessor.right to current [OK]

Common Mistakes:

• Assigning current.left to predecessor instead
• Using predecessor.left instead of right
• Confusing current.right with predecessor.right

3. What is the output of the Morris inorder traversal on the following binary tree?

    2
   / \
  1   3

medium

A. [1, 2, 3]

B. [2, 1, 3]

C. [3, 2, 1]

D. [1, 3, 2]

Solution

1. Step 1: Perform inorder traversal manually

   Inorder traversal visits left subtree, root, then right subtree. For this tree: left=1, root=2, right=3.

2. Step 2: List nodes in inorder

   Nodes visited in order: 1, 2, 3.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   Inorder = left-root-right = [1, 2, 3] [OK]

Hint: Inorder = left, root, right sequence [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Mixing up left and right child order
• Assuming Morris changes traversal order

4. Consider this buggy snippet from a Morris inorder traversal implementation:

while (current != null) {
  if (current.left == null) {
    System.out.print(current.val + " ");
    current = current.right;
  } else {
    TreeNode predecessor = current.left;
    while (predecessor.right != null) {
      predecessor = predecessor.right;
    }
    predecessor.right = current;
    current = current.left;
  }
}

What is the main bug causing an infinite loop?

medium

A. Not printing current.val when left is not null

B. Not checking if predecessor.right == current before linking

C. Not moving current to current.right when left is null

D. Not initializing predecessor correctly

Solution

1. Step 1: Identify missing condition in inner loop

   The inner while loop should stop if predecessor.right == current to avoid infinite loop.

2. Step 2: Explain infinite loop cause

   Without checking predecessor.right == current, the loop never breaks and keeps moving right, causing infinite loop.

3. Final Answer:

   Not checking if predecessor.right == current before linking -> Option B

4. Quick Check:

   Check predecessor.right == current to break loop [OK]

Hint: Always check predecessor.right == current to avoid loops [OK]

Common Mistakes:

• Ignoring thread existence check
• Assuming printing happens in else block
• Incorrect predecessor initialization

5. Given a binary tree where some nodes have only left children, how does Morris Traversal handle these nodes to produce the inorder sequence without extra space?

hard

A. It creates temporary right links from the rightmost node of left subtree back to current node

B. It skips nodes with only left children to avoid infinite loops

C. It uses recursion internally to handle left-only nodes

D. It converts the tree into a linked list before traversal

Solution

1. Step 1: Understand Morris Traversal threading

   For nodes with left children, Morris Traversal finds the rightmost node in left subtree and links its right pointer to current node temporarily.

2. Step 2: Explain handling of left-only nodes

   This threading allows traversal to return to current node after left subtree is processed, enabling inorder traversal without stack or recursion.

3. Final Answer:

   It creates temporary right links from the rightmost node of left subtree back to current node -> Option A

4. Quick Check:

   Threading rightmost left subtree node to current [OK]

Hint: Thread rightmost left child back to current node [OK]

Common Mistakes:

• Thinking recursion is used internally
• Assuming nodes are skipped
• Believing tree is converted to linked list