Wednesday, February 4, 2015

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;
}

1 comment:

  1. it would be very good idea to use iteration to create bst. But I tried { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, it seems the tree is not correct.

    ReplyDelete