Initialize a Balanced Binary Search Tree from Array C++

Question

I'm trying to write a function that recursively goes through an array, inserting values into a tree while keeping the tree balanced. It's assumed that the array is sorted and that we know its size. I understand that what I need to do is begin from around the middle of the array, insert that value into the root, then take the middle of the left and right halves and insert those into nodes left and right of the root, and so on until the array is filled. Recursion is the first thing that comes to mind and what I coded makes sense, but it doesn't seem to be working the way I intended.

Issues I'm having are that the first and last values are not being inserted, and I'm getting nodes with garbage values at the left and right of each leaf, instead of them being NULL.

The structure of the node is simple(provided by instructor):

/* A lightweight structure implementing a general binary tree node */
template <class T>
struct BTNode {
  T       elem;  // element contained in the node
  BTNode *left;  // pointer to the left child (can be NULL)
  BTNode *right; // pointer to the right child (can be NULL)

  // Constructors
  BTNode() { left = right = NULL; }
  BTNode( T elem, BTNode* left = NULL, BTNode* right = NULL ) {
    this->elem = elem;
    this->left = left;
    this->right = right;
  }
  BTNode( const BTNode& src ) {
    this->elem = src.elem;
    this->left = src.left;
    this->right = src.right;
  }

  // Simple tests
  bool is_leaf() const { return (left == NULL && right == NULL); }
};

This is the function I wrote:

// ---------------------------------------------------------------------------
// Constructor (from sorted array)
//
template<class T>
BinarySearchTree<T>::BinarySearchTree(T *elements, int n_elements) {

    int high = n_elements-1;
    int low = 0;
    root = new BTNode<T>;
    BSTreeHelper(low, high, elements, BinaryTree<T>::root);
}

Helper function for constructor:

template<class T>
void BinarySearchTree<T>::BSTreeHelper(int low, int high, T* elems, BTNode<T>* root) {

    int mid = (low+high)/2;   // to get the middle value
    bool isEqual = (low+1 == high || high-1 == low);

    // if there is a middle value, insert it
    if (!isEqual) {
        BTNode<T>* nodePtrL = new BTNode<T>;
        root->left = nodePtrL;
        BSTreeHelper(low, mid, elems, nodePtrL);

        BTNode<T>* nodePtrR = new BTNode<T>;
        root->right = nodePtrR;
        BSTreeHelper(mid, high, elems, nodePtrR);

        root->elem = elems[mid];

        cout << "Inserted Element = " << root->elem << endl;
    }
}

I can't seem to wrap my head around doing the isEqual check differently in any way in order to account for the first and last elements, and I'm really not sure why extra nodes are being created with garbage values (values outside the bounds of the array most likely). Thanks for any help you can provide. This is an assignment so I don't want the answer to be given, but a point in the right direction is much appreciated!

Answer 1

What array element would be root of the BST? The middle one.
What array element would be the root of the left subtree? The middle of the left sub-array.
What array element would be the root of the right subtree? The middle of the right sub-array.

A recursive pattern can be seen - in each call, make the middle element of the current array range the root of the current subtree, and apply the same method on the left and right subtrees.

Here's the algorithm, given in psuedo-code:

TreeNode insertSortedArrayToBST(arr[], start, end):
    if start > end
        return null

    mid := (start + end) / 2
    node := new TreeNode(arr[mid])

    node.left := insertSortedArrayToBST(arr, start, mid - 1)
    node.right := insertSortedArrayToBST(arr, mid + 1, end)

    return node

Answer 2

Your idea to use recursion is good, but it's much simpler to implement if you use a different interface for your recursive function.

Let's write a function that takes an array of elements and returns the root node of a binary tree of those elements. So this is the signature:

template <class T>
BTNode<T> *
treeWithElements(T *elements, size_t count) {

Since this function will be recursive, let's first consider the base case. You might think the base case is when count == 1, but in fact the base case is when count == 0. Then there are no elements, so we need to return an empty tree:

    if (count == 0)
        return NULL;

Ok, so now we know there's at least one element. We'll put the middle element in the new node we're about to create as the root of the tree. Here's its index:

    size_t middleIndex = count / 2;

To create the node, we need to first create the left child and the right child. The left child will contain all elements up to but not including the middle element:

    BTNode<T> *left = treeWithElements(elements, middleIndex);

(Think about this. The index of the middle element is also the number of elements preceding the middle element.)

And we need to create the right child. It will contain all elements following the middle element:

    BTNode<T> *right = treeWithElements(elements + middleIndex + 1,
        count - (middleIndex + 1));

Now we can create and return the new node:

    return new BTNode<T>(elements[middleIndex], left, right);
}

Altogether it's quite simple:

template <class T>
BTNode<T> *
treeWithElements(T *elements, size_t count) {
    if (count == 0)
        return NULL;
    size_t middleIndex = count / 2;
    BTNode<T> *left = treeWithElements(elements, middleIndex);
    BTNode<T> *right = treeWithElements(elements + middleIndex + 1,
        count - (middleIndex + 1));
    return new BTNode<T>(elements[middleIndex], left, right);
}

And your wrapper class constructor becomes one line:

template<class T>
BinarySearchTree<T>::BinarySearchTree(T *elements, int n_elements) {
    root = treeWithElements(elements, n_elements);
}