Bird
Raised Fist0

Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below? Tree structure:

easy🧾 Code Trace Q12 of Q15
Tree: Depth-First Search - Binary Tree Preorder Traversal
Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below? Tree structure:
    1
   / \
  2   3
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:
                predecessor.right = None
                current = current.right
    return result
A[2, 1, 3]
B[1, 2, 3]
C[1, 3, 2]
D[3, 1, 2]
Step-by-Step Solution
Solution:
  1. Step 1: Trace first iteration with current=1

    Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.
  2. Step 2: Trace second iteration with current=2

    Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).
  3. Step 3: Detect thread at 2.right=1

    Since predecessor.right == current, reset 2.right=None, move current=1.right=3.
  4. Step 4: Trace current=3

    Node 3 has no left child, append 3, move current=3.right=None, loop ends.
  5. Final Answer:

    Option B -> Option B
  6. Quick Check:

    Output matches preorder traversal [1,2,3] [OK]
Quick Trick: Morris preorder appends root before left subtree [OK]
Common Mistakes:
MISTAKES
  • Appending nodes in wrong order
  • Not resetting threaded links
  • Confusing left and right child traversal
Trap Explanation:
PITFALL
  • Candidates often confuse when to append nodes and when to reset threads, leading to wrong order.
Interviewer Note:
CONTEXT
  • Tests ability to mentally execute Morris traversal and understand threaded links.
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