CODEWITHSUNDEEP
algorithmdata-structurestreetraversalinorder
user4627889
user4627889

Reputation:

Finding Preoder from Just Inorder Traversal?

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?

Upvotes: 5

Views: 26383

Answers (3)

vinaych
vinaych

Reputation: 79

One of the b-trees possible is : enter image description here

So, the pre order traversal returns:

H K A E C F B D G

Another one is:
enter image description here

For which preorder traversal gives:

H A E K C F B D G

Yet another one is: enter image description here

For which preorder traversal gives:

K A E C H F B D G

,which is none of your options. Comments by anyone are welcome as I cannot come up with any other binary tree for the given inorder traversal given..

I too had this question in my exams but came to know that b is the answer from google search of the question. Lolz.

Upvotes: 0

IVlad
IVlad

Reputation: 43477

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.

Upvotes: 6

amit
amit

Reputation: 178451

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.

Upvotes: 3

Related Questions