Tree: Depth-First Search - Binary Tree Inorder Traversal
Given the output of an inorder traversal is [4, 5, 7, 10, 12], which of the following could be the original binary search tree's root value?
Given the output of an inorder traversal is [4, 5, 7, 10, 12], which of the following could be the original binary search tree's root value?
hard🔄 Reverse Engineer Q9 of Q15
Step-by-Step Solution
Solution:
Step 1: Recall inorder traversal of BST
Inorder traversal of BST outputs sorted node values.Step 2: Identify root from inorder
Root is the node where left subtree values are less and right subtree values are greater; 7 splits the list into [4,5] and [10,12].Final Answer:
Option B -> Option BQuick Check:
7 is root separating left and right subtrees [OK]
Quick Trick: Root splits inorder into left < root < right [OK]
Common Mistakes:
MISTAKES- Picking first or last element as root
- Not using BST property
Trap Explanation:
PITFALL- Candidates confuse inorder output with preorder or postorder roots.
Interviewer Note:
CONTEXT- Tests ability to reason backwards from traversal output to tree structure
Master "Binary Tree Inorder Traversal" in Tree: Depth-First Search
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Tree: Depth-First Search Quizzes