What is the approach to find preorder from given inorder?

Question

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

a)FGBDECA

b)ABFGCDE

C)BFGCDEA

d)AFGBDEC

Answer 1

I think it will not be unique. We can have many tree with this inorder.

Comments

yup! I know it was question in one of the isro paper and answer was given b i dont know how?

Answer 2

all options are possible .

Comments

Why not others ??? A should be root, is it necessary ??

---

i missed that . thanx .

Answer 3

U can't get unique binary tree for sure. But this question from ISRO so u may approach like this. Take a heap structure (i.e. complete Binary tree) and fill nodes as given inorder. FBGADCE. Here A is  middle element so it will be root. Now FBG on left and  DCE on right. Do this recursively to build tree.

Now find pre order traversal. It ll be ABFGCDE.

#still i am saying this is one (not only) way to approach this problem. Bcoz complete binary tree is standard structure but the d way they frame this question is ambiguous.

Comments

Cant we approach in this way:
In the given in order traversal, E is the last processed node therefore it will be the RIGHT-est node, and also in pre order, the RIGHT-est node will be processed the last.
And thus the answer should be b).

Answer 4

yes multiple trees are possibe but in the above problem only option b matches as in pre order and in order the last element is rightmost element ie

LrR for inorder and rLR for pre order. so last element in inorder and pre order will be same.