The Gateway to Computer Science Excellence
+19 votes
2.8k 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$
in DS by Veteran (422k points)
edited by | 2.8k views
0
B is the right answer
+8
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

5 Answers

+17 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.

by Loyal (6.8k points)
edited by
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.
+5 votes
Sorting the given sequence gives Inorder traversal.

Constructing tree gives Option B as the postorder traversal.
by Active (1.9k points)
+1 vote

many questions asked on this model

by (189 points)
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.
by (395 points)
–1 vote
B) is the answer
by Active (2.6k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,662 questions
56,122 answers
193,628 comments
93,029 users