Constructing Binary Tree from given Tree Traversal

Construct Tree from given Inorder and Preorder traversals

Let us consider the below traversals:

Inorder sequence: D B E A F C 
Preorder sequence: A B D E C F

In a Preorder sequence, the leftmost element is the root of the tree. So we know ‘A’ is the root for given sequences. By searching ‘A’ in the Inorder sequence, we can find out all elements on the left side of ‘A’ is in the left subtree, and elements on right in the right subtree. So we know the below structure now. 

                 A
               /   \
             /       \
           D B E     F C

We recursively follow the above steps and get the following tree.

         A
       /   \
     /       \
    B         C
   / \        /
 /     \    /
D       E  F

Algorithm: buildTree() 
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick the next element in the next recursive call. 
2) Create a new tree node tNode with the data as the picked element. 
3) Find the picked element’s index in Inorder. Let the index be inIndex. 
4) Call buildTree for elements before inIndex and make the built tree as a left subtree of tNode. 
5) Call buildTree for elements after inIndex and make the built tree as a right subtree of tNode. 
6) return tNode.

Construct a Binary Tree from Postorder and Inorder

Given Postorder and Inorder traversals, construct the tree.

Examples: 

Input: 
in[]   = {2, 1, 3}
post[] = {2, 3, 1}

Output: Root of below tree
      1
    /   \
   2     3 


Input: 
in[]   = {4, 8, 2, 5, 1, 6, 3, 7}
post[] = {8, 4, 5, 2, 6, 7, 3, 1} 

Output: Root of below tree
          1
       /     \
     2        3
   /    \   /   \
  4     5   6    7
    \
      8

Let us see the process of constructing tree from in[] = {4, 8, 2, 5, 1, 6, 3, 7} and post[] = {8, 4, 5, 2, 6, 7, 3, 1} 

1) We first find the last node in post[]. The last node is “1”, we know this value is root as the root always appears at the end of postorder traversal.
2) We search “1” in in[] to find the left and right subtrees of the root. Everything on the left of “1” in in[] is in the left subtree and everything on right is in the right subtree. 

         1
       /    \
[4, 8, 2, 5]   [6, 3, 7]

3) We recur the above process for following two. 
….b) Recur for in[] = {6, 3, 7} and post[] = {6, 7, 3} 
…….Make the created tree as right child of root. 
….a) Recur for in[] = {4, 8, 2, 5} and post[] = {8, 4, 5, 2}. 
…….Make the created tree as left child of root.
Below is the implementation of the above idea. One important observation is, we recursively call for the right subtree before the left subtree as we decrease the index of the postorder index whenever we create a new node.