1
 /
2   2
   /
  5   3

    6

Sorted array:     1 2 2 3 5 6
Original indexes: 1 0 4 5 2 3

First and second steps:

     1(1)
    /
2(0)

Third and fourth steps:

     1(1)
    /
2(0)      2(4)

              3(5)

Final two steps:


     1(1)
    /
2(0)      2(4)
         /
       5(2)  3(5)

          6(3)

1st step

 2 <--

2nd step

   1 <--
  /
 2

3rd and 4th steps

  1
 /
2   5

      6 <--

5th step

  1
 /
2   2 <--
   /
  5

    6

6th step

  1
 /
2   2
   /
  5   3

    6

public TreeNode buildTree(int[] inArray){
  if (inArray == null || inArray.length == 0) return null;

  int n = inArray.length;
  return dfs(inArray, 0, n - 1);
}

private TreeNode dfs(int[] inArray, int start, int end){

  if (start == end){
    return new TreeNode(inArray[start]);
  }

  if (start > end){
    return null;
  }

  int minIndex = findMin(inArray, start, end);
  TreeNode curNode = new TreeNode(inArray[minIndex]);

  TreeNode leftNode = dfs(inArray, start, minIndex - 1);
  TreeNode rightNode = dfs(inArray, minIndex + 1, right);


  curNode.left = leftNode;



  curNode.right = rightNode;


  return curNode;
}

private int findMin(int[] inArray, int start, int end){
  int minIndex = -1;
  int min = Integer.MAX_VALUE;
  for (int i = start; i <= end; i++){
      if (inArray[i] < min){
        minIndex = i;
        min = inArray[i];
      }
  }

  return minIndex;
}