Insert sorted array into binary search tree

Question

I want to implement an algorithm that inserts sorted arrays into binary search trees but I don't want ending up with a tree that only grows to one side.

Do you have any ideas?

Thanks.

Answer 1

This should give you a balanced tree (in O(n)):

1. Construct a node for the middle element in the array and return it
   (this will be the root in the base case).
2. Repeat from 1. on the left half of the array, assigning the return value to the left child of the root.
3. Repeat from 1. on the right half of the array, assigning the return value to the right child of the root.

Java-like code:

TreeNode sortedArrayToBST(int arr[], int start, int end) {
  if (start > end) return null;
  // same as (start+end)/2, avoids overflow.
  int mid = start + (end - start) / 2;
  TreeNode node = new TreeNode(arr[mid]);
  node.left = sortedArrayToBST(arr, start, mid-1);
  node.right = sortedArrayToBST(arr, mid+1, end);
  return node;
}

TreeNode sortedArrayToBST(int arr[]) {
  return sortedArrayToBST(arr, 0, arr.length-1);
}

Code derived from here.