Creating a Binary Search Tree from a sorted array

user_998649 0
Viewed 13335

I am currently checking about coding an algorithms. If we have the following case:

Given a sorted (increasing order) array with unique integer elements, wrote an algorithm to create a binary search tree with minimal height.

The following code is proposed as the solution:

TreeNode createMinimalBST(int arr[], int start, int end){
    if (end < start) {
        return null;
    }
    int mid = (start + end) / 2;
    TreeNode n = new TreeNode(arr[mid]);
    n.setLeftChild(createMinimalBST(arr, start, mid - 1));
    n.setRightChild(createMinimalBST(arr, mid + 1, end));
    return n;
}

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

But if I try this code with the following array input:

[2,4,6,8,10,20]

And I perform the first iteration

createMinimalBST([2,4,6,8,10,20], 0, 5);

The following line:

int mid = (start + end) / 2; // in Java (0 + 5) / 2  =  2;

would calculate the mid as the root of the binary search tree the position number 2 which is the value 6.

However, the binary search tree in this example should look like:

    8
   / \
  4   10
 / \    \
2   6   20

The code is coming from a reputable source, but my gut feeling is that the implementation is incorrect.

Am I missing something or the implementation is not right ?

binary-search-tree
3 Answers
  • get the middle of the array and make it as root
  • recursively do the same for the left half and the right half
    • get the middle of the left half and make it the left child of the root
    • get the middle of the right half and make it the right child of the root

enter image description here

    public TreeNode Convert(int[] array)
    {
        if (array == null || array.Length == 0)
        {
            return null;
        }

        return Convert(array, 0, array.Length - 1);
    }

    private static TreeNode Convert(int[] array, int lo, int hi)
    {
        if (lo > hi)
        {
            return null;
        }

        int mid = lo + (hi - lo) / 2;
        var root = new TreeNode(array[mid]);
        root.Left = Convert(array, lo, mid - 1);
        root.Right = Convert(array, mid + 1, hi);
        return root;
    }

Time Complexity: O(n)

from CodeStandard

user_2255550
Related