Bird
Raised Fist0

Identify the bug in the following Morris preorder traversal code snippet that causes the tree structure to remain modified after traversal:

medium🐞 Bug Identification Q14 of Q15
Tree: Depth-First Search - Binary Tree Preorder Traversal
Identify the bug in the following Morris preorder traversal code snippet that causes the tree structure to remain modified after traversal:
def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                # Bug here
                current = current.right
    return result
ALine resetting predecessor.right to None is missing in the else block
BAppending current.val before moving to left child is incorrect
CThe inner while loop condition should check predecessor.left instead of predecessor.right
DThe check for current.left being None should be after the else block
Step-by-Step Solution
Solution:
  1. Step 1: Identify missing restoration of tree structure

    In Morris traversal, after visiting left subtree, predecessor.right must be reset to None to restore original tree.
  2. Step 2: Locate missing line

    The else block lacks the line predecessor.right = None, causing the threaded link to persist.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without resetting, tree remains modified after traversal [OK]
Quick Trick: Always reset threaded links to None after use [OK]
Common Mistakes:
MISTAKES
  • Forgetting to restore tree structure
  • Appending nodes in wrong order
  • Incorrect loop conditions
Trap Explanation:
PITFALL
  • The code looks correct except for missing restoration, which is subtle and often overlooked.
Interviewer Note:
CONTEXT
  • Tests attention to detail and understanding of Morris traversal's side effects.
Master "Binary Tree Preorder 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