Bird
Raised Fist0

Given the output list [1, 2, 4, 5, 3] from a preorder traversal, which of the following binary trees could produce this output?

hard🔄 Reverse Engineer Q9 of Q15
Tree: Depth-First Search - Binary Tree Preorder Traversal
Given the output list [1, 2, 4, 5, 3] from a preorder traversal, which of the following binary trees could produce this output?
ARoot 1 with left child 2 (with children 4 and 5) and right child 3
BRoot 1 with right child 2 (with children 4 and 5) and left child 3
CRoot 1 with left child 3 and right child 2 (with children 4 and 5)
DRoot 1 with left child 2 and right child 3 (with children 4 and 5)
Step-by-Step Solution
Solution:

  1. Step 1: Analyze preorder output

    Preorder is root-left-right; output starts with 1, then 2, then 4, 5, then 3.

  2. Step 2: Match tree structure

    2 must be left child of 1 with children 4 and 5; 3 must be right child.

  3. Step 3: Identify correct tree

    Only Root 1 with left child 2 (with children 4 and 5) and right child 3 matches this structure.

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    Output matches preorder of Root 1 with left child 2 (with children 4 and 5) and right child 3 [OK]
Quick Trick: Preorder output matches root-left-right order [OK]
Common Mistakes:
MISTAKES
  • Confusing left and right subtree positions
Trap Explanation:
PITFALL
  • Candidates often misassign children causing mismatch with preorder output.
Interviewer Note:
CONTEXT
  • Tests ability to reconstruct tree structure from traversal output.
Master "Binary Tree Preorder Traversal" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Tree: Depth-First Search Quizzes
Balanced Binary Tree - Balanced Binary Tree - Quiz 6medium Balanced Binary Tree - Balanced Binary Tree - Quiz 10hard Binary Tree Cameras - Binary Tree Cameras - Quiz 11easy Binary Tree Inorder Traversal - Binary Tree Inorder Traversal - Quiz 13medium Binary Tree Inorder Traversal - Binary Tree Inorder Traversal - Quiz 11easy Construct Tree from Inorder and Postorder - Construct Tree from Inorder and Postorder - Quiz 6medium Construct Tree from Preorder and Inorder - Construct Tree from Preorder and Inorder - Quiz 14medium Flatten Binary Tree to Linked List - Flatten Binary Tree to Linked List - Quiz 12easy Path Sum - Path Sum - Quiz 1easy Serialize and Deserialize Binary Tree - Serialize and Deserialize Binary Tree - Quiz 10hard