Question

Data Structures and Algorithm: Binary Tree

Given : Inorder: GHFIEABDC Postorder: GFEIHDCBA Draw the tree and find the preorder traversal of a tree. AHGIFEBCD AGHIFEBCD DCBEFIGHA AHGIFECBD

Which of the choices is the correct answer?

Answer 1

The correct answer is:

1. AHGIFEBCD

The tree can be constructed as follow:

First we will take the information provided above which is the traversal details. So they are:

(i) Inorder: GHFIEABDC

(ii) Post Order: GFEIHDCBA

In the traversal of binary tree the alignment is as follows for different traversals:

(i) Inorder: Left-Node-Right (NLR)

(ii)Postorder: Left-Right-Node(LRN)

(iii) Preorder: Node-Left-Right (NLR)

So, the process constructing the binary tree will be step by step and can be done by

Step 1:

G

H

F

I

E

A

B

D

Here the complete inorder traversal is copied. Now we have to notice which node comes at the last in postorder traversal as in the post order node appears at the end.

Step 2:

А HF E B D C

As A node appears at the last of the post order traversal so the entire tree is divided into 2 halfs.

Step 3:

A G H F - E B D C

Before the node A the node B appears so the B will be the node and dc is placed on the right hand side of the B node.

Step 4:

A G н F - E B с D

In the post order traversal as the node C is precedent to D, the node C will be the parent node and D node will be the left child node of the C node.

Step 5:

A H B G F E - C D

After the construction of the right hand side of the binary tree H appears from the last after the node D so H will be parent node. In the inorder traversal the left part of the H node there is only G node so it will appear as a child node of H node. The right hand side of H will be constructed as it is in the inorder traversal.

Step 6:

A H B G C F E D

From the node sequence FIE, it is clearly visible that in postorder traversal the node I appears at the last so I will be the parent node. In the inorder traversal In the left hand side of I, F is there so F will be the left child node of I and G will be the right child node of I. By following these steps the final tree is constructed by using the postorder and inorder traversal provided above.

For the preorder traversal we have to consider the node first then the left child and at last the right child. So in the above binary tree A is the root node so

(i) A

Then the left hand side of the tree where the root node is H so

(ii)AH

After that the left side of the H root node is G

(iii)AHG

As there is no nodes is left on the left hand side of H so after that the right hand side of the tree will be taken into consideration where the root node is I so

(iv)AHGI

After I the left and right hand side of the parent node I will be written and it will look alike

(v)AHGIFE

After completing the left hand side of the root node A the right hand side will be written. On the right hand side of root node A, the first node which appears is B so

(vi)AHGIFEB

As there is no left child node of B so the right child node C is taken so,

(vii)AHGIFEBC

There is only one node which is left in the entire binary tree so D will be attached to the traversal as

(viii)AHGIFEBCD

So the final preorder traversal of the binary tree is : AHGIFEBCD