Morris Traversal Inorder Without Stack in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a Simple Tree

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

Tree structure:
2
/ \
1 3

Assume the traversal prints node values separated by spaces.

DSA Java

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

public class MorrisTraversal {
    public static void morrisInorder(Node root) {
        Node current = root;
        while (current != null) {
            if (current.left == null) {
                System.out.print(current.val + " ");
                current = current.right;
            } else {
                Node pre = current.left;
                while (pre.right != null && pre.right != current) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = current;
                    current = current.left;
                } else {
                    pre.right = null;
                    System.out.print(current.val + " ");
                    current = current.right;
                }
            }
        }
    }

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

A 3 2 1

B 1 2 3

C 2 1 3

D 1 3 2

💡 Hint

Morris traversal visits nodes in inorder sequence without using stack or recursion.

Morris inorder traversal visits nodes in the order: left subtree, root, right subtree. For the tree 2 with left child 1 and right child 3, the inorder is 1 2 3.

❓ Predict Output

intermediate

Morris Traversal Output on Left-Skewed Tree

What is the output of the Morris inorder traversal on this left-skewed binary tree?

Tree structure:
4
/
3
/
2
/
1

Assume the traversal prints node values separated by spaces.

DSA Java

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

public class MorrisTraversal {
    public static void morrisInorder(Node root) {
        Node current = root;
        while (current != null) {
            if (current.left == null) {
                System.out.print(current.val + " ");
                current = current.right;
            } else {
                Node pre = current.left;
                while (pre.right != null && pre.right != current) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = current;
                    current = current.left;
                } else {
                    pre.right = null;
                    System.out.print(current.val + " ");
                    current = current.right;
                }
            }
        }
    }

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

A 1 2 3 4

B 4 3 2 1

C 1 3 2 4

D 2 1 3 4

💡 Hint

Inorder traversal visits nodes from smallest to largest in a BST.

The inorder traversal visits nodes in ascending order: 1 2 3 4 for this left-skewed tree.

🔧 Debug

advanced

Identify the Bug in Morris Traversal Implementation

The following code attempts Morris inorder traversal but produces incorrect output or infinite loop. What is the bug?

DSA Java

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

public class MorrisTraversal {
    public static void morrisInorder(Node root) {
        Node current = root;
        while (current != null) {
            if (current.left == null) {
                System.out.print(current.val + " ");
                current = current.right;
            } else {
                Node pre = current.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = current;
                    current = current.left;
                } else {
                    pre.right = null;
                    System.out.print(current.val + " ");
                    current = current.right;
                }
            }
        }
    }
}

A The code should print current.val before setting pre.right = current.

B The code should use a stack to store nodes instead of modifying pointers.

C The code should set current = current.right before printing current.val.

D The inner while loop misses checking if pre.right == current, causing infinite loop.

💡 Hint

Check the condition in the inner while loop that finds the predecessor.

The inner while loop must check pre.right != current to avoid infinite loop by detecting threaded links.

🧠 Conceptual

advanced

Why Morris Traversal Uses Threaded Links?

Why does Morris inorder traversal create temporary links (threaded links) between nodes during traversal?

A To store node values in a separate array during traversal.

B To permanently change the tree structure for faster future traversals.

C To avoid using stack or recursion by temporarily linking predecessor to current node.

D To mark visited nodes so they are not processed again.

💡 Hint

Think about how Morris traversal avoids extra memory usage.

Threaded links allow traversal to return to a node after visiting its left subtree without stack or recursion.

❓ Predict Output

expert

Output of Morris Traversal on Complex Tree

What is the output of the Morris inorder traversal on this binary tree?

Tree structure:
5
/ \
3 7
/ \ \
2 4 8
/
1

Assume the traversal prints node values separated by spaces.

DSA Java

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

public class MorrisTraversal {
    public static void morrisInorder(Node root) {
        Node current = root;
        while (current != null) {
            if (current.left == null) {
                System.out.print(current.val + " ");
                current = current.right;
            } else {
                Node pre = current.left;
                while (pre.right != null && pre.right != current) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = current;
                    current = current.left;
                } else {
                    pre.right = null;
                    System.out.print(current.val + " ");
                    current = current.right;
                }
            }
        }
    }

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

A 1 2 3 4 5 7 8

B 1 2 3 4 5 6 8

C 1 2 3 4 5 6 7 8

D 1 2 3 4 5 6 7

💡 Hint

Inorder traversal visits nodes in ascending order for BST.

The inorder traversal visits nodes in sorted order: 1 2 3 4 5 7 8. Node 6 does not exist.

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