2.2k views

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

1. $2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20$
2. $2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12$
3. $7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12$
4. $7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12$
edited | 2.2k views
0
+4
Clearly root is 12 ,and in post order root is last.So reject A.

Now if you know that left most element will be printed by postorder at first place and left most in inorder is smallest which is 2.

Directly we can give b as answer without construction:)
0

ans is B

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.$

edited
Sorting the given sequence gives Inorder traversal.

Constructing tree gives Option B as the postorder traversal.

many questions asked on this model

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.