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
/ \
E ( C K )
Step 3)
Now letters are
Inorder C K
Preorder K C
So now tree is
/
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....
0 comments :
Feel free to leave comment if you like above widget, have any questions or just say Hi! :)