Postorder traversal of a given binary search tree T produces the following…
2005
Postorder traversal of a given binary search tree T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?
- A.
9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
- B.
9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
- C.
29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
- D.
95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
Attempted by 311 students.
Show answer & explanation
Correct answer: A
Key fact: Inorder traversal of a binary search tree visits the keys in ascending sorted order.
Extract the keys from the given postorder sequence: 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29.
Step 1: Collect all keys present in the tree from the postorder list.
Step 2: Sort these keys in ascending order to get the inorder sequence: 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95.
Step 3: Compare this sorted list with the candidate sequences: only the sequence that exactly matches the sorted list can be the inorder traversal of the BST.
Conclusion: The inorder traversal of the tree is the sorted sequence 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95. This corrects the missing solution and verifies which candidate sequence matches the required inorder order.
A video solution is available for this question — log in and enroll to watch it.