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?

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

Solution 2

The answer is undefined.

Have a look at those two trees:

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

And:

   A
 /  \
E    C 
      \
       K
        \
         F 
          \
           H 
            \
             D 
              \
               B
                \
                 G

Those two trees have the same in-order traversal, but the first has the pre-order traversal of EACKFHDBG, while the second has the in-order traversal of AECKFHDBG

So, given an in-order traversal, there is much more than one possible binary tree that fit that traversal. This is because of the fact that there are n! possible permutations (and thus in-order traversal), while there are much more binary trees. This guarantees (pigeonhole principle) that there is (at least one) in-order traversal that fits multiple trees.

Comments

[Admin]

thanks from your useful answer, but i think we must consider it with multiple choice ! i think.

[Erick Wong]

Actually you have the last sentence backwards. The number of binary trees is a Catalan number which grows only exponentially (very roughly 4^n). n! is much larger (in fact it's not so hard to see that any permutation results in only one binary search tree, but multiple permutations could fit the same unlabelled tree).

[amit]

@ErickWong This (Catalan) is the number of binary trees with identical nodes (i.e. you care only for the topology, and not the mark of each node).

[IVlad]

@Prof.KosiNoura - yes.

[sigdelsanjog]

Wow I understood how to to it, after I tick the wrong answer today... :)

[Vishist Varugeese]

Shouldn't the root element of the subtree in the third step be K and its left child be C?