Morris Traversal Inorder Without Stack in DSA Python - 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 Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def morris_inorder(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            pre = current.left
            while pre.right and pre.right != current:
                pre = pre.right
            if pre.right is None:
                pre.right = current
                current = current.left
            else:
                pre.right = None
                result.append(current.val)
                current = current.right
    return result

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(morris_inorder(root))

A [2, 4, 5, 1, 3]

B [1, 2, 3, 4, 5]

C [4, 5, 2, 3, 1]

D [4, 2, 5, 1, 3]

💡 Hint

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

The Morris inorder traversal visits nodes in the order: left subtree, current node, right subtree without using stack or recursion.

For the given tree, the inorder sequence is 4, 2, 5, 1, 3.

🧠 Conceptual

intermediate

Understanding Morris Traversal Threading

In Morris inorder traversal, what is the purpose of creating a temporary thread (link) from the inorder predecessor to the current node?

A To skip visiting the left subtree entirely

B To permanently modify the tree structure for faster future traversals

C To avoid using recursion or stack by temporarily linking back to the current node after visiting left subtree

D To mark nodes as visited to prevent revisiting them

💡 Hint

Think about how Morris traversal avoids extra memory usage.

The temporary thread allows the traversal to return to the current node after finishing the left subtree without using stack or recursion.

This thread is removed after use, so the tree remains unchanged.

🔧 Debug

advanced

Identify the Error in Modified Morris Traversal Code

What error will the following modified Morris inorder traversal code produce when run on a binary tree?

DSA Python

def morris_inorder_bug(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            pre = current.left
            while pre.right != None and pre.right != current:
                pre = pre.right
            if pre.right == None:
                pre.right = current
                current = current.left
            else:
                # Missing line to remove thread
                result.append(current.val)
                current = current.right
    return result

A Infinite loop due to missing removal of temporary thread

B TypeError because of wrong attribute access

C SyntaxError due to missing colon

D Correct output without errors

💡 Hint

Check if the temporary thread is removed after use.

The code misses the line that removes the temporary thread (pre.right = None).

This causes the traversal to revisit the same nodes endlessly, resulting in an infinite loop.

🚀 Application

advanced

Number of Nodes Visited Twice in Morris Traversal

In Morris inorder traversal of a binary tree with N nodes, how many nodes are visited more than once during the traversal?

A Exactly N-1 nodes are visited twice

B Exactly one node is visited twice

C No nodes are visited twice

D Exactly N nodes are visited twice

💡 Hint

Consider how many temporary threads are created and how often nodes are revisited.

In Morris traversal, each node except the rightmost node in inorder is visited twice: once when first reached, and once when returning via the temporary thread.

Thus, N-1 nodes are visited twice.

❓ Predict Output

expert

Output of Morris Traversal on Complex Tree with Multiple Levels

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

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def morris_inorder(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            pre = current.left
            while pre.right and pre.right != current:
                pre = pre.right
            if pre.right is None:
                pre.right = current
                current = current.left
            else:
                pre.right = None
                result.append(current.val)
                current = current.right
    return result

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)
root.right.left = Node(12)
root.right.right = Node(20)
root.left.left.left = Node(1)
root.left.left.right = Node(3)

print(morris_inorder(root))

A [1, 2, 3, 5, 7, 10, 12, 15, 20, 25]

B [1, 2, 3, 5, 7, 10, 12, 15, 20]

C [10, 5, 2, 1, 3, 7, 15, 12, 20]

D [1, 3, 2, 7, 5, 12, 20, 15, 10]

💡 Hint

Inorder traversal visits nodes in ascending order for BST.

The Morris inorder traversal visits nodes in ascending order for this binary search tree.

The correct inorder sequence is [1, 2, 3, 5, 7, 10, 12, 15, 20].

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 uses no extra space for stack or recursion.

B. It is faster than all other traversal methods.

C. It only works on binary search trees.

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

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

3. Final Answer:

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

4. Quick Check:

   Space complexity = O(1) [OK]

Hint: Morris uses threads, no stack or recursion needed [OK]

Common Mistakes:

• Thinking Morris is faster in time complexity
• Believing it only works on BSTs
• Assuming it permanently changes the tree

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

easy

A. current = root

B. current = None

C. current = root.left

D. 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 options

   Setting current = root ensures traversal begins at the tree's root.

3. Final Answer:

   current = root -> Option A

4. Quick Check:

   Start at root node [OK]

Hint: Always start traversal from root node [OK]

Common Mistakes:

• Starting from None causes no traversal
• Starting from root.left misses root node
• Starting from root.right misses left subtree

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 in order.

medium

A. [2, 1, 3]

B. [1, 3, 2]

C. [3, 2, 1]

D. [1, 2, 3]

Solution

1. Step 1: Understand inorder traversal order

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

2. Step 2: Apply Morris traversal order

   For the tree, left is 1, root is 2, right is 3, so output is [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

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

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

Common Mistakes:

• Confusing preorder or postorder with inorder
• Misreading tree structure
• Assuming traversal prints in insertion order

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

current = root
while current:
    if current.left is None:
        print(current.val)
        current = current.right
    else:
        pre = current.left
        while pre.right and pre.right != current:
            pre = pre.right
        if pre.right is None:
            pre.right = current
            current = current.left
        else:
            pre.right = None
            print(current.val)
            current = current.right

What is the main bug if the line pre.right = None is missing?

medium

A. The traversal will print nodes in preorder instead of inorder.

B. The traversal will skip the root node.

C. The traversal will enter an infinite loop.

D. The traversal will cause a syntax error.

Solution

1. Step 1: Understand role of pre.right = None

   This line removes the temporary thread created to return to the root after left subtree traversal.

2. Step 2: Consequence of missing this line

   If not removed, the thread remains, causing the loop to revisit nodes endlessly, creating an infinite loop.

3. Final Answer:

   The traversal will enter an infinite loop. -> Option C

4. Quick Check:

   Missing thread removal = infinite loop [OK]

Hint: Always remove temporary threads to avoid loops [OK]

Common Mistakes:

• Thinking it causes syntax error
• Assuming it changes traversal order
• Believing it skips nodes

5. You want to modify Morris inorder traversal to collect node values in a list instead of printing them. Which of the following code changes correctly achieves this without changing the traversal logic?

result = []
current = root
while current:
    if current.left is None:
        # Change here
        current = current.right
    else:
        pre = current.left
        while pre.right and pre.right != current:
            pre = pre.right
        if pre.right is None:
            pre.right = current
            current = current.left
        else:
            pre.right = None
            # Change here
            current = current.right

hard

A. Replace only second '# Change here' line with result.append(current.val)

B. Replace both '# Change here' lines with result.append(current.val)

C. Replace only first '# Change here' line with result.append(current.val)

D. Replace both '# Change here' lines with print(current.val)

Solution

1. Step 1: Identify where nodes are visited

   In Morris traversal, nodes are visited and printed in two places: when left is None and after removing thread.

2. Step 2: Replace print with appending to list

   To collect values, replace both print statements with result.append(current.val) to capture all visited nodes.

3. Final Answer:

   Replace both '# Change here' lines with result.append(current.val) -> Option B

4. Quick Check:

   Collect all visited nodes in list [OK]

Hint: Append values at both visit points to collect all nodes [OK]

Common Mistakes:

• Appending only once misses some nodes
• Leaving print statements causes unwanted output
• Changing traversal logic breaks correctness