2.4k 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.4k views
0
B is the right answer
+6
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.$

answered by Loyal (6.9k points)
edited
0
If in-order traversal of binary search tree is : 5, 6, 8, 10, 12, 13, 15, 17, 19

then, how to make tree? is there any method ? if yes please mention it.
Sorting the given sequence gives Inorder traversal.

Constructing tree gives Option B as the postorder traversal.
answered by Active (1.8k points)

many questions asked on this model

answered by (105 points)
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.
answered by (211 points)
–1 vote
B) is the answer
answered by Active (2.6k points)

1
2
+1 vote