Im trying to build an array based, "Binary Search Tree". So far I enjoy the concept and drawing the diagrams on paper! However, when i do that the nodes are all linear! I was wondering if anyone could help me "balance" the tree?

BST::BST(int capacity) : items(new item[capacity]), size(capacity-1), tree_index(0), root_index(0)
{
      items[root_index].empty = true;
 items[tree_index].empty = true;
}

void BST::reallocate()
{
    item *new_array = new item[size*2];
    for ( int array_index = 0; array_index < size; array_index++ ) 
    {
        //new_array[array_index].theData = items[array_index].theData;
        new_array[array_index].empty = false;
    }
    size *= 2;
    delete [] items;

    items = NULL;
    items = new_array;
}

void BST::insert(const data& myData)
{
data *aData = new data(myData);

if ( items[root_index].empty == true ) // make the first data the root.
{
    root_index++;
    items[root_index].theData = *aData;
    items[root_index].empty = false;
    items[tree_index].empty = true;
}

else if ( (*aData) < items[root_index].theData ) // then we have a left child. 
{
    if ( items[tree_index].empty == false ) // we already have a child
    {
        root_index++;
        items[root_index].theData = items[tree_index].leftChild;
        tree_index++;
        items[tree_index].empty = true;
        this->insert(*aData); // call again for another comparison because we have a new root.      
    }
    if ( tree_index == size ) // prevent overflow
    {
        this->reallocate();   // make the call to reallocate items array
        items[tree_index].empty = false;
    }
    // construct the left subtree if..
    else 
    {
        items[tree_index].leftChild = *aData;
        //items[tree_index].theData = *aData;
        items[tree_index].empty = false;
        root_index = 1;
    }
    
}
else // right child 
{
    // construct the right subtree in a similar way.
    if ( items[tree_index].empty == false )
    {
        root_index++;
        items[root_index].theData = items[tree_index].rightChild;
        tree_index++;
        items[tree_index].empty = true;
        this->insert(*aData); // call again for another comparison because we have a new root.      
    }
    if ( tree_index == size ) // prevent overflow
    {
        this->reallocate();   // make the call to reallocate items array
        items[tree_index].empty = false;
    }
    // construct the left subtree if..
    else 
    {
        items[tree_index].rightChild = *aData;
        //items[tree_index].theData = *aData;
        items[tree_index].empty = false;
        root_index = 1;
    }
}

}

Not actual Code

insert("R");
insert("A");
insert("F");
insert("L");
insert("B");
insert("T");
insert("C");
insert("G");

For a while, it went kinda nice. A and F are both less than R in ascii value. So whenever i had another potential child i simply made the already present child the "root" or "parent". And did my recursive call and compared the new data...But after a while it the code gets confusing and doesnt work...

            R
           /
          A
           \
            F
          /
         L   <---- Wrong b/c the root gets mixed up..its not "R" anymore! 

I might be missing an important iterative solution..instead of recursion..

Not good. Im trying to keep the root, "R" for all comparisons. Either recursively or iteratively.

Here is my struct where items and its members that im using are defined within the BST private section: ...

struct item
    {
        bool empty;
        data theData;
        data leftChild;
        data rightChild;
    };

    item *items;     // The tree array
    int root_index;  // index for the root
    int tree_index; // index to for the data items