Given the serialized string "1,2,3,X,X,4,5" from BFS serialization, which of the following is the correct original binary tree structure?

hard🔄 Reverse Engineer Q9 of Q15

Tree: Depth-First Search - Serialize and Deserialize Binary Tree

ARoot 1 with left child 2 and right child 3; 2 has left child 4 and right child 5

BRoot 1 with left child 2 and right child 3; 3 has left child 4 and right child 5

CRoot 1 with left child 3 and right child 2; 3 has left child 4 and right child 5

DRoot 1 with left child 2 and right child 3; 3 has left child 5 and right child 4

Step-by-Step Solution

Solution:

Step 1: Parse BFS serialized string
Order: 1 (root), 2 (left), 3 (right), X (2's left null), X (2's right null), 4 (3's left), 5 (3's right).
Step 2: Reconstruct tree
Root 1 has left 2 and right 3; 2 has no children; 3 has left 4 and right 5.
Final Answer:
Option B -> Option B
Quick Check:
Matches BFS order and null markers [OK]

Quick Trick: BFS order matches node insertion left to right [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often confuse which child corresponds to which position in BFS order.

Interviewer Note:

CONTEXT

Master "Serialize and Deserialize Binary Tree" 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

More Tree: Depth-First Search Quizzes