Gate CS-2005 Question Paper With Solutions

Q. 33 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

Answer: (A)

Explanation: