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?

score 5 · Accepted Answer · answered Mar 14 '15 at 11:08

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.

Wow I understood how to to it, after I tick the wrong answer today... :) — sigdelsanjog, Aug 05 '15 at 16:39
Shouldn't the root element of the subtree in the third step be K and its left child be C? — Vishist Varugeese, Jul 12 '19 at 19:44

score 2 · Answer 2 · edited May 23 '17 at 12:34

2

The answer is undefined.

Have a look at those two trees:

And:

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.

edited May 23 '17 at 12:34

Community

1
1

answered Mar 14 '15 at 07:17

amit

175,853
27
231
333

thanks from your useful answer, but i think we must consider it with multiple choice ! i think. – Mar 14 '15 at 07:41
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). – Erick Wong Mar 14 '15 at 16:49
@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). – amit Mar 14 '15 at 16:51

score 0 · Answer 3 · edited Jun 20 '20 at 09:12

One of the b-trees possible is :

So, the pre order traversal returns:

H K A E C F B D G

Another one is:

For which preorder traversal gives:

H A E K C F B D G

Yet another one is:

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.

Finding Preoder from Just Inorder Traversal?

3 Answers3