GATE CSE 2013 | Question: 43

Question

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?

• A. $10, 20, 15, 23, 25, 35, 42, 39, 30$
• B. $15, 10, 25, 23, 20, 42, 35, 39, 30$
• C. $15, 20, 10, 23, 25, 42, 35, 39, 30$
• D. $15, 10, 23, 25, 20, 35, 42, 39, 30$

Comments

We can construct a unique BST from a given preorder or postorder. We traverse preorder in forward direction and postorder in reverse direction to construct the BST.

Answer 1

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).

Comments

30 we came to know is the root of the tree . how did u come to know root of left subtree ?

---

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

---

acha got it

Answer 2

takes time but there will no confusion

Comments

I drew in less than 1 minute,, how can you claim it takes time?

---

@ijnuhb right.