GATE IT 2008 | Question: 46

Question

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which.

1. $MBCAFHPYK$
2. $KAMCBYPFH$
3. $MABCKYFPH$

Pick the true statement from the following.

• A. I and II are preorder and inorder sequences, respectively
• B. I and III are preorder and postorder sequences, respectively
• C. II is the inorder sequence, but nothing more can be said about the other two sequences
• D. II and III are the preorder and inorder sequences, respectively

Answer 1

In preorder, root comes at the beginning of the traversal sequence and in postorder, root comes at the last of the traversal sequence. So, out of the given sequences only $1$ and $2$ are having such kind of order i.e $K$ at the beginning and at the last.

Therefore, $2$ is the preorder and $1$ is postorder and the left sequence i.e $3$ will definitely be inorder.

So, option D is correct.

Comments

Adding little bit more to answer:-

For inorder:- left->root->right

For preorder:-root->left->right

Therefore for perorder and inorder the ending are same but it is for somecases

Answer 2

Using this as preorder KAMCBYPFH and inorder MABCKYFPH .

So this gives II and III are the preorder and inorder sequences, respectively.

Ans is option D

Answer 3

Answer: D

Binary Tree is:

    K                          
   /   \                          
  A    Y  
 /   \     \   
M  C    P           
     /     /  \
   B     F  H