23 votes

The pre-order traversal of a binary search tree is given by $12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20$. Then the post-order traversal of this tree is

- $2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20$
- $2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12$
- $7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12$
- $7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12$

22 votes

Best answer

Preoder: $\enclose {circle}{12}\quad \enclose {circle}{8} \quad 6\quad 2\quad 7\quad 9\quad 10\quad 16\quad 15\quad 19\quad 17\quad 20$

Inorder of BST must be sorted in increasing order!

Inorder: $\underbrace{\overbrace{2\quad 6 \quad 7}^{\text{left}}\quad \overset{\text{root}}{\enclose {circle}{8}}\quad \overbrace{9\quad 10}^{\text{right}}}_{\text{left}}\quad \overset{\text{root}}{\enclose {circle}{12}}\quad \underbrace{15\quad 16\quad 17\quad 19\quad 20}_{\text{right}}$

So, Postorder: $2 \quad 7 \quad 6 \quad10\quad9\quad8\quad15\quad17\quad20\quad19\quad16\quad12.$

Answer is **B.**

6 votes

Sorting the given sequence gives Inorder traversal.

Constructing tree gives Option B as the postorder traversal.

Constructing tree gives Option B as the postorder traversal.

0 votes

To find a unique BST (pre-order, in-order) or (post-order, in-order) is required. Here in question the pre-order traversal is given & we can find in-order traversal(in-order of BST is in increasing order of keys). So we got that pair. Now we can construct a BST & for that tree, post-order traversal can be found easily.