The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?

A.

10, 11, 12, 15, 16, 18, 19, 20

B.

11, 12, 10, 16, 19, 18, 20, 15

C.

20, 19, 18, 16, 15, 12, 11, 10

D.

19, 16, 18, 20, 11, 12, 10, 15

Solution:

Pre-order traversal: 15, 10, 12, 11, 20, 18, 16, 19

In Binary Search Tree, In-order traversal is increasing order = 10, 11, 12, 15, 16, 18, 19, 20

According to Pre-order (ROOT, LEFT, RIGHT):
Root = 15

According to In-order (LEFT, ROOT, RIGHT):

Post order traversal: 11, 12, 10, 16, 19, 18, 20, 15