2.6k views

The preorder traversal sequence of a binary search tree is $30, 20, 10, 15, 25, 23, 39, 35, 42$. Which one of the following is the postorder traversal sequence of the same tree?

1. $10, 20, 15, 23, 25, 35, 42, 39, 30$
2. $15, 10, 25, 23, 20, 42, 35, 39, 30$
3. $15, 20, 10, 23, 25, 42, 35, 39, 30$
4. $15, 10, 23, 25, 20, 35, 42, 39, 30$
in DS
edited | 2.6k views

Since it is a binary search tree, its inorder traversal produces a sorted sequence i.e. $\text{10, 15, 20, 23, 25, 30, 35, 39, 42}$.

Now given inorder and preorder traversals, we get following tree :

From this, we can give postorder traversal sequence as $\text{15,10,23,25,20,35,42,39,30}$ i.e. option (D).

by Boss
edited
0
30 we came to know is the root of the tree . how did u come to know root of left subtree ?
+1

check the pre order  30, 20, 10, 15, 25, 23, 39, 35, 42.So 20 will next and followed in same way.

+1
acha got it