Construct Binary Tree using PostOrder And Inorder in Java

We have “post order” and “in order” of binary search tree. We have to construct the Binary Tree with this information.

First we should know that there is unique Binary Tree with one PostOrder and InOrder.
So below I am explaining how to construct the Binary Tree:

PostOrder Traversal: {D, E, B, F, C, A}
InOrder Traversal: {D, B, E, A, F, C}

1. If we have PostOrder then last element will be root. If PostOrder traversal is :           {D, E, B, F, C, A} then ‘A’ will be root.
2. We will search ‘A’ in InOrder traversal we got it @ index 3.
3. Whatever present from 0-2 will be present in left sub tree of Root Node ‘A’ and from index 4-5 will be present in right sub tree of A as follows.
4. 

   After first step

5. And now we will check for second last element from postOrder that is ‘C’
6. We will check ‘C’ in InOrder array, and ‘C’ is present at last location that means ‘F’ will be its left child as follows:
7. Order of nodes whether they will be in left or right, can be determined from inOrder array. 
8. 

   After second step

9. Again traverse post order array from right and after A and C we will get ‘F’ and search it in InOrder but there is no need as F is leaf node.
10. Next from post order list comes ‘B’, check ‘B’ in InOrder array.
11. We got ‘B’ in InOrder array at position ‘1’, now as we can see that at left of ‘B’ (in InOrder) there is ‘D’ so D will be its left child and in right of ‘B’ there is ‘E’ so ‘E’ will be its right child.
12. 

    Final Binary Tree

Similar approach can be applied over Binary Search Tree also.

Java Code

//Java program to construct a tree using inorder and postorder traversal

/* A binary tree node has data, reference to left child
and a reference to right child */
class Node 
{
 char data;
 Node left, right;

 Node(char item) 
 {
     data = item;
     left = right = null;
 }
}

public class BinaryTreeUsingPreorderAndInorder 
{
     Node root;  // Declaring root reference
     static int postIndex = 0; // keeps track of index in postOrder array
     
     // Constructor to initialize size of postIndex to array length - 1
     public BinaryTreeUsingPreorderAndInorder(int len){postIndex=len-1;}

     /* Recursive function to construct binary tree of size len from
        Inorder traversal in[] and PostOrder traversal pre[].
        Initial values of inStrt and inEnd should be 0 and len -1.  
        inStrt and inEnd are indices of InOrder array.
        */
    
    // return type of this function is of type Node
    Node buildTree(char[] in, char[] post, int inStrt, int inEnd){
 
        // Condition to break recursion
        if(inStrt > inEnd)
      return null;

        /* Pick current node from PostOrder traversal using postIndex
        and decrement postIndex */
        
        // Create a new Node
        Node tNode = new Node(post[postIndex--]);
        
        /* If this node has no children then return */
        if(inStrt == inEnd)
                return tNode;
        
        // Search the elements from postOrder in inOrder array
        // search will return index of element
        int inIndex = search(in,inStrt, inEnd, tNode.data);
        
        /* Using index from Inorder traversal, construct right and
        left subtrees  again using recurstion
        */
        // First create right sub tree from inIndex+1 to inEnd 
        tNode.right = buildTree(in, post, inIndex+1, inEnd);
        // And then create left sub tree from inStrt to inIndex-1 
        tNode.left = buildTree(in, post, inStrt, inIndex-1);

        // At last return the root of the tree        
        return tNode;
    }
    
     /* Function to find index of value in arr[start...end]
      The function assumes that value is present in in[] */
     int search(char arr[], int strt, int end, char value) 
     {
         int i;
         for (i = strt; i <= end; i++) 
         {
             if (arr[i] == value)
                 return i;
         }
         return i;
     }

     /* This funtcion is here just to test buildTree() */
     void printInorder(Node node) 
     {
         if (node == null)
             return;
    
         /* first recur on left child */
         printInorder(node.left);
    
         /* then print the data of node */
         System.out.print(node.data + " ");
    
         /* now recur on right child */
         printInorder(node.right);
     }
     
     // driver program to test above functions
     public static void main(String args[]) 
     {
         char in[] = new char[]{'D', 'B', 'E', 'A', 'F', 'C'};
         char post[] = new char[]{'D', 'E', 'B', 'F', 'C', 'A'};

         BinaryTreeUsingPreorderAndInorder tree = 
         new BinaryTreeUsingPreorderAndInorder(post.length); 
         int len = in.length;
         /* calling buildTree method to create 
          * tree using postOrder and InOrder 
         */ The function returns reference to the root node.
         Node root = tree.buildTree(in, post, 0, len - 1);
         // inorder traversal of build tree
         System.out.println("Inorder traversal of constructed tree is : ");
         tree.printInorder(root);
     }
}