java - Recursive minimal tree creating function buggy?

Question

From an exercise in Cracking the Coding Interview: Given a sorted (increasing order) array with unique integer elements, write an algorithm that will create a binary search tree with minimal height.

The algorithm structure is:

1. Insert into the tree the middle element of array (is root).

2. Insert (into left subtree) the left subarray elements.

3. Insert (into right subtree) the right subarray elements.

4. Recurse.

But the actual code I believe is buggy. Given an array that holds {6, 7, 8, 9, 10}, it'll insert the 6 twice into the left subtree. This is because of int mid = (start + end) / 2; The code will never insert node 7 into the left subtree tree because it is at index 1, and the mid variable won't evaluate to 1.

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

Node createMinimalBST(int arr[], int start, int end) {
 if (end < start) {
  return null;
 }

 int mid = (start + end) / 2;
 Node n = new Node(arr[mid]);
 n.left = createMinimalBST(arr, start, mid - 1);
 n.right = createMinimalBST(arr, mid + 1, end);
 return n;
}

标签： javarecursionbinary-search-tree

Answer 1

There is nothing wrong with the algorithm or the code logic. Below is exactly how the binary search tree will look like after the insertions as per the code.

  8
 / \
6   9
 \   \
 7   10

Working code of the logic :

#include <iostream>
using namespace std;

typedef struct node {
    int val;
    node *left, *right;
    node(int value){
        val = value;
        left = right = NULL;
    }
}Node;

Node* createMinimalBST(int arr[], int start, int end) {
    if (end < start)
        return NULL;

    int mid = (start + end) / 2;
    Node *n = new Node(arr[mid]);
    n->left = createMinimalBST(arr, start, mid - 1);
    n->right = createMinimalBST(arr, mid + 1, end);
    return n;
}

Node* createMinimalBST(int arr[], int size) {
    return createMinimalBST(arr, 0, size - 1);
}

int main() {

    int a[] = {6, 7, 8, 9, 10};
    Node *root = createMinimalBST(a, 5);

    cout << root->val << endl;
    cout << root->left->val << endl;
    cout << root->right->val << endl;
    cout << root->left->right->val << endl;
    cout << root->right->right->val << endl;

    return 0;
}

Output of the code :

8
6
9
7
10