Question

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. 95, 50, 60, 40, 27, 23, 22, 25, 10, 0, 15, 29
• C. 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
• D. 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29

Answer 1

The correct option is A 9, 10, 15 ,22, 23, 25, 27, 29, 40, 50, 60, 95

The inorder traversal of a binary search tree is always in the sorted order or increasing order of a given sequence so the inorder traversal of the tree T is 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 55