ISRO CSE 2011 | Question: 26

Question

The in-order traversal of a tree resulted in FBGADCE. Then the pre-order traversal of that tree would result in

• A. FGBDECA
• B. ABFGCDE
• C. BFGCDEA
• D. AFGBDEC

Comments

IF U PROVIDE OPTION THEN IT IS POSSIBLE TO GET..

---

inorder is given that means left root right means middle one is our root .  so here in given inorder middle one is A in  FBGADCE then break into 2 part on left  FBG and on right DCE then apply same thing on FBG here B is middle and other hand C is middle then now we have tree . from tree we easily get preorder

---

Actually, both option B & option D are true here.

Only if (preorder & inorder) or (postorder & inorder) are given, then a unique binary tree exist. Otherwise, more than 1 binary tree are possible. 
That's why, in this question more than 1 options are correct. 

I have attached below the tree satisfying both options B & D. 

Answer 1

If we try to generate tree from question, we get following tree.

                        A

                  B             C

       F               G      D       E

 

Its inorder = FBGADCE

and preorder = ABFGCDE

Comments

                           A

        F                                 D

              G                                   E

       B                                  C

Preorder : AFGBDEC
Inorder : FBGADCE
 

What's the problem with this tree? Isn't option D) can match too

---

Both option B and D are satisfying the conditions

---

Exactly, ve seen 2,3 questions in isro like this and on GO everyone's sayng stuff like ambiguous etc etc. But we have to use eliminations in options because for givn norder/post/pre there wil exist some order that are just not possible

Answer 2

Preorder cant be determined unless it is given Inorder and Postorder of given tree.

Answer 3

This Question is ambiguous to construct a tree we must have either $InOrder & PreOrder or  InOrder & PostOrder$

but for a binary search tree we can only have PreOrder or PostOrder as in order of BST is non-decreasing order of keys.

Answer 4

inorder is given that means left root right means middle one is our root .  so here in given inorder middle one is A in  FBGADCE then break into 2 part on left  FBG and on right DCE then apply same thing on FBG here B is middle and other hand C is middle then now we have tree . from tree we easily get preorder

Comments

if even nodes then??