Construction of Binary Tree From Inorder and Preorder/Postorder Traversal Fully Explained

After finding a lot in books and Internet I found this easy method on how to create B.Tree from studying following data

a)  - INORDER Traversal 

-POSTORDER Traversal 

OR 

b)  -INORDER Traversal 

-PREORDER Traversal 

We usually get Questions like :-

Create Binery tree from following tree Traversals

1)  Inorder:   E  A  C  K  F  H  D  B  G

    Preorder:  F  A  E  K  C  D  H  G  B

2)   INORDER:      D J H B E A F I C G 

      POSTORDER: J H D E B I F G C A

  

HERE the most important think to ALWAYS remember is :-

• In PREorder  FIRST element is ROOT of the tree
• In POSTorder  LAST element is ROOT of the tree

I hope you got it :P

i.e considering 1) Question

1)  Inorder:   E  A  C  K  F  H  D  B  G

    Preorder:  F  A  E  K  C  D  H  G  B

Considering 2) Question

2)   INORDER:      D  J  H  B  E  A  F  I  C  G 

      POSTORDER: J  H  D  E  B  I  F  G  C  A

* BLACK highlighted letters are roots 

** RED highlighted letters will go to LEFT SUB TREE  of Root 

***GREEN highlighted letters will go to RIGHT SUB TREE of Root

Let us Start with Question 1)

Step 1)

Now as we know which one is Root So...

                                   F

                                /     \

             ( E A C K)           (H D B G) 

Step 2)

Now FOR LEFT SUB TREE we have 

E A C K from Inorder and same letters from Preorder A  E  K  C 

i.e  Inorder   E A C K 

      Preorder A  E  K  C 

now have found Root again so now tree is 

                                   F

                                /     \

                             A       (H D B G) 

                           /    \

                         E     ( C K )

Step 3)

 Now letters are

Inorder    C  K

Preorder  K C

So now tree is 

                                   F

                                /     \

                             A       (H D B G) 

                           /    \

                         E     K

                               /

                             C

Same procedure can be done on Right Sub tree Of root F

For Postorder we have to find Root as the last element in traversal....

For UPDATED Info VISIT