Bird
Raised Fist0

Given the following Morris inorder traversal code, what is the final output list after running inorderTraversal on this tree?

easy🧾 Code Trace Q12 of Q15
Tree: Depth-First Search - Binary Tree Inorder Traversal
Given the following Morris inorder traversal code, what is the final output list after running inorderTraversal on this tree?

Tree structure:
2
/ \ 1 3
from typing import Optional, List

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

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)  # visit node
            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:
                predecessor.right = None  # remove thread
                result.append(current.val)  # visit node
                current = current.right
    return result
A[1, 2, 3]
B[1, 3, 2]
C[2, 1, 3]
D[3, 2, 1]
Step-by-Step Solution
  1. Step 1: Trace traversal starting at root=2

    Current=2 has left child 1, find predecessor in left subtree: node 1 (no right child). Create thread from 1.right to 2, move current to 1.
  2. Step 2: Visit node 1 (no left child), append 1, move current to 1.right which points to 2 (thread).

    Remove thread, append 2, move current to 2.right=3. Node 3 has no left child, append 3, move current to null.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Inorder traversal of tree 1,2,3 is [1,2,3] [OK]
Quick Trick: Inorder traversal visits left, root, right [OK]
Common Mistakes:
MISTAKES
  • Appending before removing thread
  • Visiting root before left subtree
  • Confusing preorder with inorder output
Trap Explanation:
PITFALL
  • Candidates often confuse when to append node values, leading to incorrect order.
Interviewer Note:
CONTEXT
  • Tests ability to mentally execute Morris traversal and track pointer changes.
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