GATE CSE 2017 Set 2 | Question: 36

Question

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

• A. $2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20$
• B. $2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12$
• C. $7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12$
• D. $7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12$

Comments

ans is B

---

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

---

Yes we can construct a unique BST by given exactly one of postorder/preorder using BST properties. No need to find inorder.

@rahul your method will not work in this question: https://gateoverflow.in/3816/gate-it-2005-question-55

Answer 1

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.

Comments

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.

---

How the right side edge of the binary tree is constructed?

---

in-order traversal : 5, 6, 8, 10, 12, 13, 15, 17, 19

I think we cannot  construct BST using only in-order traversal because 

1. in-order traversal is just elements of BST in sorted order
2. issue is how to figure out root of tree (In-order : < Left, Root, Right >)

5, 6, 8, 10, 12, 13, 15, 17, 19  ( No info. about root ..)

Answer 2

Sorting the given sequence gives Inorder traversal.

Constructing tree gives Option B as the postorder traversal.

Answer 3

many questions asked on this model

Answer 4

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.