import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

public class UnorderedArrayToTree {

 private int[] An = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 }; 
 private static class Tree{
  private Tree parent;
  private Tree leftChild;
  private Tree rightChild;
  private int currentValue;
  public Tree(){}
  public Tree(int data){
   this.parent=null;
   this.leftChild=null;
   this.rightChild=null;
   this.currentValue=data;
  }

 }
 
 public Tree createTree(int An[]){
  Tree root = null;
  List list = new ArrayList();
  int length = An.length;
  for(int i=1;i<=length;i++){
   list.add(new Tree(An[i-1]));
  }
  for(int i=1;i<=list.size()/2-1 && list!=null;i++){
   list.get(i-1).leftChild = list.get(i*2-1);
   list.get(i*2-1).parent = list.get(i-1);
   list.get(i-1).rightChild = list.get(i*2);
   list.get(i*2).parent = list.get(i-1);
  }
  int lastIndex = list.size()/2;
  list.get(lastIndex-1).leftChild=list.get(lastIndex*2-1);
  list.get(lastIndex*2-1).parent = list.get(lastIndex-1);
  if(list.size()%2==1){
   list.get(lastIndex-1).rightChild= list.get(lastIndex*2);
   list.get(lastIndex*2).parent=list.get(lastIndex-1);
  }
  return root = list.get(0);
 }
}