Finding Preoder from Just Inorder Traversal?

Question

I ran into a Mid-Exam Question, that took 4 days ago, I couldent underestand it!

Suppose we have the answer given when we have an inorder traversal of a tree then how come we will find out the solution in case of a preorder traversal. I have the following example with me : When inorder traversing a tree resulted E A C K F H D B G;

what would the preorder traversal return?

a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG

Who can help me in a learning manner?

EDIT: I know the answer is : FAEKCDHGB. but how this calculated?

Answer 1

So the inorder is:

E A C K F H D B G

And the preorder must be from:

a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG

You should proceed by drawing the tree for each of these options while also making it fit with the inorder traversal and see for which one that is possible.

To do that, for each character in the preorder traversal, split the inorder traversal in two around that character.

a.

We know F must be the root. Split the inorder traversal around F:

        | F | 
 E A C K     H D B G

The next character in the preorder traversal is A. Split the subtree containing A around A:

            | F | 
     | A |        H D B G
    E     C K

The next is E. Nothing to split. The next is K:

            | F | 
     | A |        H D B G
    E     C
            K

The next is C. Nothing to split.

The next is D:

            | F | 
     | A |        | D |
    E     C      H     B G
            K

The next is B:

            | F | 
     | A |        | D |
    E     C      H     B 
            K            G

And we're done, there will be no more splits possible. Now run the preorder traversal on this tree, you'll get:

F A E C K D H B G

Which is not what we started with, so we reached a contradiction. So it cannot be a. Do the same for the others.