Which of the following is/are correct inorder traversal sequence(s) of binary…
2015
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?
I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9 18, 20, 25
- A.
I and IV only
- B.
II and III only
- C.
II and IV only
- D.
II only
Attempted by 449 students.
Show answer & explanation
Correct answer: A
Key idea: inorder traversal of a binary search tree visits nodes in ascending order.
Check whether each sequence is strictly increasing. Only sequences that are sorted in ascending order can be inorder traversals of a BST.
3, 5, 7, 8, 15, 19, 25 is strictly increasing → possible inorder.
5, 8, 9, 12, 10, 15, 25 is not increasing (12 is followed by 10) → not possible.
2, 7, 10, 8, 14, 16, 20 is not increasing (10 is followed by 8) → not possible.
4, 6, 7, 9, 18, 20, 25 is strictly increasing → possible inorder.
Conclusion: only the first and fourth sequences can be inorder traversals of BSTs, so the correct answer is the choice that lists those two sequences.
A video solution is available for this question — log in and enroll to watch it.