NOTICE

Adfly Links not working Find Direct Links HERE

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


6 comments :

  1. Thank u very much !!!!!! Your post was very helpful to me.

    ReplyDelete
  2. If only inorder are there then how can you find out the postorder?please help me.

    ReplyDelete
  3. Appreciate the recommendation. Will try it out.

    My weblog :: cheats für castleville

    ReplyDelete
  4. Thanks dear it was very very useful to me. i was searching from a long time thanks again dear

    ReplyDelete
  5. thank u...really helpful...would be better if u code the same also

    ReplyDelete

Feel free to leave comment if you like above widget, have any questions or just say Hi! :)