Can someone help me with an array based Binary Search Tree C++?

Question

This what i have so far.

void BST::insert(const data& aData)
{
    if ( items[root_index].empty ) 
    {
        items[root_index].theData = aData;// Get the data.
        items[root_index].empty = false;
        oldRoot.theData = aData;
    }  
    else  
    {   
        if ( aData < items[root_index].theData )
        {
            leftChild = root_index * 2;
            if ( items[leftChild].empty )
            {
                items[leftChild].theData = aData;
                items[leftChild].empty = false;
            }
            else 
            {
              root_index++;
              items[root_index].theData = items[leftChild].theData;                          
                                   items[root_index].empty = false;
              this->insert(aData);
            }
        }
         else if ( items[root_index].theData < aData )
         {
            rightChild = root_index * 2 + 1;
            if ( items[rightChild].empty )
            {
                items[rightChild].theData = aData;
                items[rightChild].empty = false;
            }
            else
            {//this where the problem is for "Z" insertion
                root_index++;
                items[root_index].theData = items[rightChild].theData;
                items[root_index].empty = false;
                this->insert(aData);
            }
        }
        else return;
    }
    items[1].theData = oldRoot.theData;
}

and the constructor:

BST::BST(int capacity) : items(new item[capacity]), size(0),
leftChild(0), rightChild(0), root_index(1)
{
     items->empty = true;
     maxSize = capacity-1;
}

It doesnt work. I dont know why. I cant seem to write the code to make it balanced. What I have so far is a tree that resembles:

       R
      /
     A
      \
       F

When inserting, "R", "A", and "F", so when i try to insert "Z" it becomes F's right child. But it should really be the root's right child:

       R
      / \
     A   Z
      \
       F

Can someone help me make it like that?

Answer 1

I could be missing something, but the code just looks like all kinds of messed up. The root_index++, the recursive call to insert() after you add the data to the tree... You might want to go back to the drawing board on this one.

If you're going for a complete binary search tree (which is the main reason for using an array), you can append new elements to the array and move elements that break the tree order invariants (left descendents < node and node < right descendents) up the tree.