Construct-tree-from-given-inorder-and-preorder-traversal

Program:

 private static int p = 0;
 
 static Node buildTree(int[] in, int[] pre) throws Exception{
  
  int l1 = in.length;
  int l2 = pre.length;
  
  if(l1 != l2) throw new Exception("\nImpossible to build tree.\n");
  
  return buildTreeUtil(in, pre, 0, l1-1);
  
 } 

 private static Node buildTreeUtil(int[] in, int[] pre, int l, int r) throws Exception {
  
  if(l > r) return null;
  
  Node root = new Node(pre[p]);

  int pos = searchKey(in, pre[p], l, r);
  
  if(pos == -1) throw new Exception("\n Impossible to build tree. Key doesn't exist.");
  
  p++;
  
  if(l == r) return root;
  
  root.left = buildTreeUtil(in, pre, l, pos-1);
  
  root.right = buildTreeUtil(in, pre, pos+1, r);
  
  return root;
 }

 private static int searchKey(int[] in, int key, int l, int r) {

  for(int i = l; i <= r; i++)
  {
   if(in[i] == key) return i;
  }
  return -1;
 }

Reference:

http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/