search
Log In
23 votes
3.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
edited by
3.8k views
1
B is the right answer
13
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:)
1

ans is B

1
Should we need to create a in order... Can we just make a tree by using bst properties???

5 Answers

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.


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.
0
How the right side edge of the binary tree is constructed?
6 votes
Sorting the given sequence gives Inorder traversal.

Constructing tree gives Option B as the postorder traversal.
1 vote

many questions asked on this model

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.
–1 vote
B) is the answer
Answer:

Related questions

21 votes
9 answers
1
10.9k views
A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the ... rear node points to the front node. (I) only. (II) only. Both (I) and (II). Neither (I) nor (II).
asked Feb 14, 2017 in DS Madhav 10.9k views
24 votes
9 answers
2
5.2k views
Let $T$ be a binary search tree with $15$ nodes. The minimum and maximum possible heights of $T$ are: Note: The height of a tree with a single node is $0$. $4$ and $15$ respectively. $3$ and $14$ respectively. $4$ and $14$ respectively. $3$ and $15$ respectively.
asked Feb 14, 2017 in DS Arjun 5.2k views
1 vote
2 answers
3
791 views
Suppose that we have numbers between $1$ and $1000$ in a binary search tree and we want to search for the number $365$. Which of the following sequences could not be the sequence of nodes examined ? $4, 254, 403, 400, 332, 346, 399, 365$ $926, 222, 913, 246, 900, 260, 364, 365$ $927, 204,913, 242, 914, 247, 365$ $4, 401, 389, 221, 268, 384, 383, 280, 365$
asked Jul 28, 2016 in Programming makhdoom ghaya 791 views
0 votes
2 answers
4
...