Creating a Binary Search Tree from a sorted array

问题:

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 ?

回答1:

Reference GeeksForGeeks

Algorithm -

1. Get the Middle of the array and make it root.
2. Recursively do same for left half and right half.
   • Get the middle of left half and make it left child of the root created in step 1.
   • Get the middle of right half and make it right child of the root created in step 1.

Wikipedia Link

CODE

 class Node {

    int data;
    Node left, right;

    Node(int d) {
        data = d;
        left = right = null;
    }
}

class BinaryTree {

    static Node root;

    /* A function that constructs Balanced Binary Search Tree 
    from a sorted array */
    Node sortedArrayToBST(int arr[], int start, int end) {

        /* Base Case */
        if (start > end) {
            return null;
        }

        /* Get the middle element and make it root */
        int mid = (start + end) / 2;
        Node node = new Node(arr[mid]);

        /* Recursively construct the left subtree and make it
        left child of root */
        node.left = sortedArrayToBST(arr, start, mid - 1);

        /* Recursively construct the right subtree and make it
        right child of root */
        node.right = sortedArrayToBST(arr, mid + 1, end);

        return node;
    }

    /* A utility function to print preorder traversal of BST */
    void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        int arr[] = new int[]{2, 4, 6, 8, 10, 12};
        int n = arr.length;
        root = tree.sortedArrayToBST(arr, 0, n - 1);
        System.out.println("Preorder traversal of constructed BST");
        tree.preOrder(root);
    }
}

回答2:

A sorted array will give you a balanced binary tree. This could be done easily in O(n) time, as we can get the middle element in O(1) time. Following is a simple algorithm,

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 implementation

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

Time Complexity: ** O(n) ** Following is the recurrance relation for sortedArrayToBST().

T(n) = 2T(n/2) + C

T(n) --> Time taken for an array of size n

C --> Constant (Finding middle of array and linking root to left and right subtrees take constant time)