Question

Postorder traversal of a given binary search tree T produces following sequence of keys: 3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?
1. 3, 4, 5, 7, 9, 14, 20, 18, 17, 16, 15
2. 20, 18, 17, 16, 15, 14, 3, 4, 5, 7, 9
3. 20, 18, 17, 16, 15, 14, 9, 7, 5, 4, 3
4. 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20

Answer 1

Correct Answer - Option 4 : 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20

The correct answer is "option 4".

CONCEPT:

The in-order traversal of the Binary Search Tree(BST) always gives elements in ascending or increasing order.

So, in-order traversal of the sequence of keys given in post-order traversal is sorted ascending order of that keys.

Hence, the sequence of keys in an in-order traversal of BST are : 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20