Question

P1. Construct the tree with post-order traversal string = i b d a h g c f, and in-order traversal string = b i a d f g h c.

P2. Construct the tree with pre-order traversal string = 10, 20, 40, 50, 80, 60, 70, 90, and in-order traversal string = 40, 50, 20, 10, 80, 70, 90, 60.

Answer 1

P1. Postoder traversal = (Left node, Right Node,Root Node)

And in the Inorder traversal :

First ->Left node.

The center part -> Root node.

The Last -> Right node.

Now given Post order traversal = i b d a h g c f

And the Inorder traversal = b i a d f g h c

Step1: First Find the Root node from Post order traversal i.e first element from right.

Step2:From Inorder,The nodes at left->Left nodes and The nodes at Right->Right nodes

Step3:From the Post order check which node comes first when traversed from right end to left end. The first coming element will be the next root node.

Step4:obtain the Left node and Right node from the provided inorder traversal string.

Step 5: Repeat steps 1 to 4 until there is no nodes to be covered .

After computing the Tree obtained will be:

P2. Preoder traversal = (Root node, Left Node,Right Node)

And in the In order traversal the order of nodes is:

First comes the Left node.

The center part ->Root node.

The Last part will be the Right node.

Now given Pre order traversal = 10,20,40,50,80,60,70,90

And the Inorder traversal = 40,50,20,10,80,70,90,60

Step1: First Find the Root node from Pre order traversal i.e first element from left.

Step2:From Inorder,The nodes at left->Left nodes and The nodes at Right->Right nodes

Step3:From the Pre order check which node comes first when traversed from left end to the right end of string. The first coming element will be the next root node.

Step4:Get the left node and right node from the provided inorder string.

Step 5: Repeat steps 1 to 4 until there is no nodes to be covered.

After computing the Tree obtained will be:

Hope it helps!!!