Data Structures, Algorithms, & Applications in Java
Chapter 12, Exercise 35

Suppose we are told that the postorder and inorder listings of a binary tree are postList[0:6] = [5, 3, 1, 6, 4, 2, 0] and inList[0:6] = [3, 5, 1, 0, 2, 6, 4]. From the definition of postorder we know that postlist[6] = 0 is the root. From the definition of inorder we know that in inorder the root is preceded by its left subtree and followed by its right subtree. So inList[0:2] is the inorder listing of the left subtree and inList[4:6] is the inorder listing of the right subtree. The left and right subtrees can now be constructed recursively using this information. It is convenient to construct the right subtree first because when we scan the postorder listing from right to left, we first encounter the nodes in the right subtree and then the nodes in the left subtree.

To implement the above strategy efficiently it is useful to construct an array inMap[] with the property that inMap[i] gives the location of postList[i] in inList[i]. For the example above inMap[0:6] = [1, 0, 2, 5, , 4, 3]. This mapping array enables us to quickly find the location of postList[i] in inList[].

If we make the assumption that the data elements of an n node binary tree are 0, 1, ..., n-1, we can construct inMap in linear time as below. 
// construct inMap
// first construct inverse of InList
int [] inverse = new int [n];
for (int i = 0; i < n; i++)
   inverse[inList[i]] = i;
// now construct inMap
for (int i = 0; i < n; i++)
   inMap[i] = inverse[postList[i]];
When we cannot make this assumption we can construct inMap by sorting both inList and postList. This sort will take linear time if the range of data values is small (in this case bin sort (see Chapter 6) can be used) and the sort will take O(n log n) time when we must sort using the general purpose sorts of Chapters 13 (heap sort) and 19 (merge sort).

The code to build the binary tree is given below. This code assumes that the elements are distinct integers in the range 1 through n-1, where n is the number of elements/nodes in the tree. A test program and its ouput are given in the files BuildFromPostAndIn.*. 
public class BuildFromPostAndIn
{
   // class data members
   static int [] inMap;
   static int [] postList;
   static int endPost;

   /** construct the unique binary tree with postorder listing
     * thePostList[] and inorder listing theInList.
     * The tree elements are assumed to be the distinct integers
     * 0 through theInList.length - 1.
     * return root of constructed binary tree */
   public static BinaryTreeNode buildFromPostAndIn
                 (int [] thePostList, int [] theInList)
   {// set class data members and invoke theBuildFromPostAndIn

      postList = thePostList;
      endPost = postList.length - 1; 
                // postorder list for subtree ends at postList[endPost]

      // set inMap so that inMap[i] is the location of
      // thePostList[i] in theInList[]
      // first construct inverse of theInList
      int [] inverse = new int[theInList.length];
      for (int i = 0; i < theInList.length; i++)
         inverse[theInList[i]] = i;
      // now construct inMap
      inMap = new int [theInList.length];
      for (int i = 0; i < theInList.length; i++)
         inMap[i] = inverse[postList[i]];

      return theBuildFromPostAndIn(0, inMap.length - 1);
   }


   /** construct the unique binary tree with inorder listing
     * inList[startIn:endIn] and whose postorder listing is
     * postList[... endPost]. inMap[i] is the location of
     * postList[i] in inList[]. Note that inList is not a
     * parameter of the method.
     * return root of constructed binary tree */
   static BinaryTreeNode theBuildFromPostAndIn(int startIn, int endIn)
   {
      if (startIn > endIn)
         // tree is empty
         return null;
     
      // create a node for the root and set its element field
      BinaryTreeNode root = new BinaryTreeNode(new Integer(postList[endPost]));

      // verify that element is in the proper subtree
      int inLocation = inMap[endPost--];
      if (inLocation < startIn || inLocation > endIn)
         throw new IllegalArgumentException
                   ("incompatible postorder and inorder listings");
   
      // construct right subtree recursively
      root.rightChild = theBuildFromPostAndIn(inLocation + 1, endIn);

      // construct left subtree recursively
      root.leftChild = theBuildFromPostAndIn(startIn, inLocation - 1);
   
      return root;
   }
}


The complexity of BuildFromPostAndIn is Theta(n). So the overall complexity of the construction process is determined by the complexity of constructing InMap. In general, this takes O(n log n) time .