Bird
Raised Fist0

Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?

medium🐞 Bug Identification Q14 of Q15
Tree: Depth-First Search - Binary Tree Inorder Traversal
Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?
def inorderTraversal(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                # BUG: missing line to remove thread
                result.append(current.val)
                current = current.right
    return result
AMissing line resetting predecessor.right = None to remove thread
BLine moving current to current.left after creating thread
CLine appending current.val after detecting thread
DLine setting predecessor.right = current (creating thread)
Step-by-Step Solution
  1. Step 1: Identify thread removal step

    Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.
  2. Step 2: Locate missing removal

    The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without removing thread, traversal loops endlessly [OK]
Quick Trick: Always remove threads to restore tree [OK]
Common Mistakes:
MISTAKES
  • Forgetting to remove thread
  • Appending node before removing thread
  • Incorrectly creating thread
Trap Explanation:
PITFALL
  • Candidates may think creating thread is enough, missing that removal is essential to avoid infinite loops.
Interviewer Note:
CONTEXT
  • Tests attention to detail and understanding of Morris traversal correctness.
Master "Binary Tree Inorder Traversal" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Tree: Depth-First Search Quizzes