# GATE2017-2-36

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
1
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???

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 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?
Sorting the given sequence gives Inorder traversal.

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

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.
–1 vote

## Related questions

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