Building a binary tree using inorder and post/pre order traversals

We have to create the following binary tree

We use recursive approach for constructing a binary tree from In-order and Post-order or Pre-order traversals .

Constructing from Inorder and Preorder:

In Pre order, we first traverse the root, then left sub tree and right sub tree. So the first element in the pre order is always the root. We search for this element in the in-order sequence. This index divides the in-order sequence into left subtree and right subtree.

For example consider the following binary tree
                
                       1
               /  
              2     3
             /    /    
            4   5 6   7

Inorder:  {4, 2, 5, 1, 6, 3, 7}
Preorder: {1, 2, 4, 5, 3, 6, 7}

Create 1 as the root node, 

• all the left elements to the left of it {4, 2, 5} form the left subtree
• all the elements to the right of it {6, 3, 7} form the right subtree

We can use the index of 1 in Inorder (in this case 3) to calculate the size of the left and right subtrees.

Size(left subtree) = index
Size(right subtree) = size-index-1

We can also use this index to calculate the offset of Inorder and Post order sequences for the subtree.

To create the left subtree we pass Inorder:{4, 2, 5} Preorder:{2, 4, 5} as parameters to the recursive call.

To create the right subtree we pass Inorder:{6, 3, 7} Preorder:{3, 6, 7} as parameters.

Constructing from Inorder and Postorder:

In post order, we first traverse the left subtree, right subtree and visit the root. So the last element in the post order sequence is the root.
Similar to the above algorithm, this element divides the in-order sequence into left subtree and right subtree.

Considering the same example as above the Post order is {4, 5, 2, 6, 7, 3, 1}
Once we create the root with the last element i.e 1. 

We pass the following parameters to create the left and right subtrees.

                       Inorder                 Postorder
Left Subtree    {4, 2, 5}                {4, 5, 2}
Right Subtree   {6, 3, 7}                {6, 7, 3}

Here is the C++ implementation of the above two algorithms.