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.

Solution 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.

Solution 2

public class SortedArrayToBST {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null) {
            return null;
        }
        return buildBST(num, 0, num.length - 1);
    }

    private TreeNode buildBST(int[] num, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(num[mid]);
        TreeNode left = buildBST(num, start, mid - 1);
        TreeNode right = buildBST(num, mid + 1, end);
        root.left = left;
        root.right = right;
        return root;
    }
}

Comments

[laura]

sir , what would be the time complexity if there was no restricton of balanced binary search tree?should it be O(n) only?

[laura]

i mean could have make skewed tree by the given sorted input.what would be its time complexity?

[Bernhard Barker]

@laura It will also take O(n) to construct an unbalanced tree. Simply going through the input array once takes O(n), so there's no way to do better than that.

[laura]

sir , one more request .can you please provide me recurrence relation for your given algorithm .I want to derive the worst case time complexity :)

[Bernhard Barker]

@laura It seems to be T(n) = 2T(n/2) + 1.