retagged by
18,577 views
8 votes
8 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$
retagged by

5 Answers

Best answer
14 votes
14 votes

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
2 votes
2 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

29 votes
29 votes
4 answers
1
Arjun asked Feb 12, 2020
21,505 views
In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a,b]$? Assume that the number of reported ...
27 votes
27 votes
2 answers
2
Arjun asked Feb 12, 2020
13,403 views
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially?$\Theta (n^{4})$$\Theta (n^{2})$$\Theta (n^{2}\log n)$$\...
36 votes
36 votes
9 answers
3
Arjun asked Feb 12, 2020
26,134 views
What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?$\Theta(n)$$\Theta(n...