in DS retagged ago by
13,974 views
4 votes
4 votes

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?

  1. $10,11,12,15,16,18,19,20$
  2. $11,12,10,16,19,18,20,15$
  3. $20,19,18,16,15,12,11,10$
  4. $19,16,18,20,11,12,10,15$
in DS retagged ago by
by
14.0k views

2 Comments

edited by

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

0
0

procedure for elimination

0
0

5 Answers

11 votes
11 votes
Best answer

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.

edited by

1 comment

good question to practice https://gateoverflow.in/2504/gate1994-8
1
1
3 votes
3 votes
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 :
0 votes
0 votes
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.
0 votes
0 votes
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.
Answer:

Related questions