build balanced binary search tree from sorted array

Given a sorted array, build balanced search tree based on it. The easiest way to do it is use recursion. Here I present the recursive and iterative solutions as well.


Solution 1: do it iteratively. --- working in progress, the below implementation is not correct!!!

public static Node sorted2bstIteratively(int[] nums){

assert(nums != null);

int start = 0, end = nums.length-1, mid = (start + end)>>>1;

Node root,  pre;

root = pre = new Node(nums[mid]);

end = mid -1;

while(start<=end){

mid = (start + end)>>>1;

Node n = new Node(nums[mid]);

pre.left = n;

pre = n;

end = mid - 1;

}

pre = root;

start = (nums.length-1)>>>1+1; end = nums.length-1;

while(start<=end){

mid = (start + end)>>>1;

Node n = new Node(nums[mid]);

if(pre!=null)

pre.right = n;
    pre = n;

start = mid + 1;

}

return root;

}

Solution 2: do it recursively.

public static Node sorted2bst(int[] nums){

assert(nums != null);

return sorted2bstRec(nums, 0, nums.length-1);

}

public static Node sorted2bstRec(int[] nums, int start, int end){

if(start>end)

return null;

int mid = (start+end)>>>1;

Node curr = new Node(nums[mid]);

curr.left = sorted2bstRec(nums, start, mid-1);

curr.right = sorted2bstRec(nums, mid+1, end);

return curr;

}