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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a Simple Tree

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

DSA C#

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

Node root = new Node(2);
root.left = new Node(1);
root.right = new Node(3);

void MorrisInorder(Node root) {
    Node current = root;
    while (current != null) {
        if (current.left == null) {
            System.Console.Write(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.Console.Write(current.val + " ");
                current = current.right;
            }
        }
    }
}

MorrisInorder(root);

A 1 2 3

B 3 2 1

C 2 1 3

D 1 3 2

💡 Hint

Remember inorder traversal visits left subtree, then node, then right subtree.

Morris traversal visits nodes in inorder without stack by temporarily modifying right pointers of predecessor nodes. For this tree, inorder is 1, 2, 3.

❓ Predict Output

intermediate

Output of Morris Traversal on Tree with Left Subtree Only

What will be printed by the Morris inorder traversal on this tree?

DSA C#

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 4 3 2 1

B 1 3 2 4

C 1 2 3 4

D 2 1 3 4

💡 Hint

Inorder traversal visits nodes from smallest to largest in BST.

The traversal visits leftmost node first, then up the tree, printing 1 2 3 4.

🔧 Debug

advanced

Identify the Error in Modified Morris Traversal Code

What error will this modified Morris traversal code produce?

DSA C#

void MorrisInorder(Node root) {
    Node current = root;
    while (current != null) {
        if (current.left == null) {
            System.Console.Write(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.Console.Write(current.val + " ");
                current = current.right;
            }
        }
    }
}

MorrisInorder(root);

A Infinite loop

B NullReferenceException

C Correct output

D StackOverflowException

💡 Hint

Check the inner while loop condition for predecessor traversal.

The inner while loop misses the check pre.right != current, causing infinite loop when pre.right points back to current.

🧠 Conceptual

advanced

Why Morris Traversal Uses Threaded Links Temporarily?

Why does Morris inorder traversal temporarily modify the tree by creating threaded links?

A To balance the tree dynamically during traversal

B To permanently change the tree structure for faster future traversals

C To store node values in a separate array during traversal

D To avoid using stack or recursion by linking predecessor to current node

💡 Hint

Think about how Morris traversal avoids extra memory usage.

Morris traversal creates temporary links from predecessor to current node to return after left subtree without stack or recursion.

🚀 Application

expert

Number of Steps in Morris Inorder Traversal for Complete Binary Tree

For a complete binary tree with n nodes, how many times is the inner while loop (finding predecessor) executed in Morris inorder traversal?

A At most 3n times

B At most 2n times

C At most n log n times

D At most n times

💡 Hint

Each edge is visited at most twice in Morris traversal.

Each edge is traversed twice: once to create threaded link and once to remove it, so inner loop runs at most 2n times.

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 works only on binary search trees.

B. It is faster than all other traversal methods.

C. It uses no extra space for stack or recursion.

D. It modifies the tree permanently.

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal uses threaded binary trees to avoid recursion or stack, so it uses O(1) extra space.

2. Step 2: Compare with other methods

   Recursive and stack-based traversals use O(h) space where h is tree height, so Morris Traversal saves memory.

3. Final Answer:

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

4. Quick Check:

   Space complexity = O(1) [OK]

Hint: Morris Traversal uses threading to avoid extra space [OK]

Common Mistakes:

• Thinking it is faster than recursive traversal
• Assuming it only works on BSTs
• Believing it permanently changes the tree

2. Which of the following C# code snippets correctly initializes the current node for Morris inorder traversal?

easy

A. TreeNode current = root;

B. TreeNode current = null;

C. TreeNode current = root.left;

D. TreeNode current = root.right;

Solution

1. Step 1: Identify starting point for traversal

   Morris traversal starts from the root node to cover the entire tree.

2. Step 2: Check initialization correctness

   Initializing current as root ensures traversal begins at the tree's root.

3. Final Answer:

   TreeNode current = root; -> Option A

4. Quick Check:

   Start traversal at root node [OK]

Hint: Start traversal from root node always [OK]

Common Mistakes:

• Starting from null causes no traversal
• Starting from left or right child misses nodes

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

    2
   / \
  1   3

Assuming the traversal prints node values separated by spaces.

medium

A. 3 2 1

B. 1 2 3

C. 2 1 3

D. 1 3 2

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, root, then right subtree.

2. Step 2: Apply Morris traversal order on given tree

   Left child 1, then root 2, then right child 3 results in "1 2 3".

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Confusing preorder or postorder with inorder
• Misreading tree structure

4. Consider this snippet of Morris inorder traversal code in C#:

while (current != null) {
    if (current.left == null) {
        Console.Write(current.val + " ");
        current = current.right;
    } else {
        TreeNode predecessor = current.left;
        while (predecessor.right != null && predecessor.right == current) {
            predecessor = predecessor.right;
        }
        if (predecessor.right == null) {
            predecessor.right = current;
            current = current.left;
        } else {
            predecessor.right = null;
            Console.Write(current.val + " ");
            current = current.right;
        }
    }
}

What is the bug in this code?

medium

A. The code does not handle the case when current.left is null.

B. The Console.Write statements should be outside the if-else blocks.

C. The predecessor.right pointer is never reset to null, causing infinite loop.

D. The inner while loop should check predecessor.right != current instead of predecessor.right == current.

Solution

1. Step 1: Analyze inner while loop condition

   The loop should continue while predecessor.right != null && predecessor.right != current to reach the rightmost node in left subtree.

2. Step 2: Check given condition correctness

   The code uses predecessor.right == current, which fails to traverse the right chain properly, as it only continues if already threaded back.

3. Step 3: Why other options are wrong

   A: left null is handled in if. C: reset happens in else. D: print placement is correct for inorder.

4. Final Answer:

   The inner while loop should check predecessor.right != current instead of predecessor.right == current. -> Option D

5. Quick Check:

   Loop condition must be != null && != current [OK]

Hint: Check loop conditions carefully to avoid infinite loops [OK]

Common Mistakes:

• Confusing loop condition signs
• Forgetting to reset threaded pointers
• Misplacing print statements

5. You want to modify Morris inorder traversal to count the number of nodes in a binary tree without using extra space or recursion. Which modification is correct?

hard

A. Increment a counter each time you print a node's value during traversal.

B. Increment a counter only when you create a threaded link.

C. Increment a counter only when you remove a threaded link.

D. Increment a counter only when current.left is null.

Solution

1. Step 1: Identify when nodes are visited in Morris traversal

   Nodes are visited (printed) when current.left is null or after removing threaded link.

2. Step 2: Counting nodes correctly

   Incrementing counter when printing nodes ensures counting all nodes exactly once.

3. Step 3: Why other options fail

   Incrementing only on creating or removing threaded links misses nodes or counts duplicates.

4. Final Answer:

   Increment a counter each time you print a node's value during traversal. -> Option A

5. Quick Check:

   Count nodes when visiting them [OK]

Hint: Count nodes when printing during traversal [OK]

Common Mistakes:

• Counting on threaded link creation/removal
• Counting only left-null nodes
• Missing some nodes in count