Q. A Binary tree comprises 9 nodes. The preorder and inorder traversals of the tree yield the given sequence of nodes:
Inorder : E A C K F H D B G
Preorder: F A E K C D H G B
Draw the particular tree. Explain your algorithm as well.
Ans.
Inorder: E A C K F H D B G
Preorder: F A E K C D H G B
The tree T is drawn from its root downward as shown below.
a) The root T is obtained by selecting the first node in its preorder. Therefore, F is the root of T.
b) The left child of the node F is obtained as shown here. First use the inorder of T to find the nodes the in the left subtree T1 of F. Thus T1 consists of the nodes E, A, C and K. Then the left child of F is obtained by choosing the first node in the preorder of T1 (which appears in the preorder of T). Therefore A is the left son of F.
c) Likewise, the right subtree T2 of F comprises of the nodes H, D, B and G, and D is the root of T2, that is, D is the right child of F.
Performing the above process with each new node, we finally obtain the desired tree.