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

Suppose we are told that the preorder and inorder listings of a binary tree are preList[0:6] = [0, 1, 3, 5, 2, 4, 6] and inList[0:6] = [3, 5, 1, 0, 2, 6, 4]. From the definition of preorder we know that prelist[0] = 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.

To implement the above strategy efficiently it is useful to construct an array inMap[] with the property that inMap[i] gives the location of preList[i] in inList[i]. For the example above inMap[0:6] = [3, 2, 0, 1, 4, 6, 5]. This mapping array enables us to quickly find the location of preList[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[preList[i]];
When we cannot make this assumption we can construct inMap by sorting both inList and preList. 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 BuildFromPreAndIn.*. 
public class BuildFromPreAndIn
{
   // class data members
   static int [] inMap;
   static int [] preList;
   static int startPre;

   /** construct the unique binary tree with preorder listing
     * thePreList[] and preorder 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 buildFromPreAndIn
                 (int [] thePreList, int [] theInList)
   {// set class data members and invoke theBuildFromPreAndIn

      preList = thePreList;
      startPre = 0;   // preorder list for subtree begins at preList[startPre]

      // set inMap so that inMap[i] is the location of
      // thePreList[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[preList[i]];

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


   /** construct the unique binary tree with inorder listing
     * inList[startIn:endIn] and whose preorder listing is
     * preList[startPre ...]. inMap[i] is the location of
     * preList[i] in inList[]. Note that inList is not a
     * parameter of the method.
     * return root of constructed binary tree */
   static BinaryTreeNode theBuildFromPreAndIn(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(preList[startPre]));

      // verify that element is in the proper subtree
      int inLocation = inMap[startPre++];
      if (inLocation < startIn || inLocation > endIn)
         throw new IllegalArgumentException
                   ("incompatible preorder and inorder listings");

      // construct left subtree recursively
      root.leftChild = theBuildFromPreAndIn(startIn, inLocation - 1);
   
      // construct right subtree recursively
      root.rightChild = theBuildFromPreAndIn(inLocation + 1, endIn);
   
      return root;
   }
}


The complexity of theBuildFromPreAndIn is O(n). So the overall complexity of the construction process is determined by the complexity of constructing inMap. Under the assumptions we have made, inMap is constructed in O(n) time. In general, however, it takes O(n log n) time to construct inMap.