The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
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$
asked in DS by Veteran (349k points)
edited by | 2k views
0
B is the right answer
+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

5 Answers

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

answered by Loyal (6.7k points)
edited ago by
+3 votes
Sorting the given sequence gives Inorder traversal.

Constructing tree gives Option B as the postorder traversal.
answered by Active (1.8k points)
0 votes
B) is the answer
answered by Active (2.5k points)
0 votes

many questions asked on this model

answered by (85 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.
answered ago by (139 points)


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

36,194 questions
43,647 answers
124,088 comments
42,929 users