GATE CSE 2020 | Question: 5

Question

The preorder traversal of a binary search tree is $15, 10, 12, 11, 20, 18, 16, 19$. Which one of the following is the postorder traversal of the tree?

• A. $10,11,12,15,16,18,19,20$
• B. $11,12,10,16,19,18,20,15$
• C. $20,19,18,16,15,12,11,10$
• D. $19,16,18,20,11,12,10,15$

Comments

…....….…..….…..……...…..

---

procedure for elimination

Answer 1

Preorder traversal of BST $: 15,10,12,11,20,18,16,19$

In Pre-order, the first node is ROOT. So root is $15.$

In Post-order, the last node is ROOT. So in the Post-order sequence, $15$ must be at last.

In Pre-order, the second node is the left child of ROOT, if it is less than the root.

Sequence$: 10,12,11$ belongs to the left sub-tree of ROOT.

$10,12,11$ is a Preorder of  BST -- repetitively apply the steps.

In the Pre-order, the nodes which are greater than ROOT are on the right side of ROOT.

Sequence$: 20,18,16,19$ belongs to the right sub-tree of ROOT.

$20,18,16,19$ is a Preorder of BST -- repetitively apply the steps.

Finally we will get $11,12,10,16,19,18,20,15$ as Postorder.

Comments

good question to practice https://gateoverflow.in/2504/gate1994-8

Answer 2

Answer : B

Since it is binary Search tree so Inorder traversal will be Sorted order of the given sequence: 10, 11, 12, 15, 16, 18, 19, 20.

Binary search tree is :

Answer 3

Since  preorder is given and  we can get inorder (since  BST, so ascending order is inorder) . Use both design structure of tree and traverse in post order.

Answer 4

Option B it is.

Taking a BST as

    A

  B.   C

 D  E.  F. G

H

the preorder traversal order becomes

ABDHECFG

For the post order traversal of the same H becomes the first node i.e. 11 and so on.