Binary Search Tree. Insert method inserting incorrectly

I have an issue where my items in my binary tree are being inserted incorrectly. I'm inserting strings in each node. I think I might be doing something wrong because it seems like I always end up with the wrong tree. i.e.

A, B, C

I should have

   B
  /  \
 A    C

but somehow I end up with like:

   C
  / \
 B   A

or som开发者_运维百科ething different depending in which order I insert in my tree.

This is my tree class:

This is my insert method and insert helper method. Can you take a look and see what I'm doing wrong? Thanks in advance.

void BinarySortTree::insert(string key)
{
    if(root != NULL)
    {
        insert(key, root);
    }
    else
    {
        root = new TreeNode;
        root->item = key;
        root->left = NULL;
        root->right = NULL;
    }
}

void BinarySortTree::insert(string key, TreeNode *node)
{
    bool done = false;

    while(!done)
    {
        if(key.compare(node->item) < 0)
        {
            if(node->left != NULL)
            {
                node = node->left;
            }
            else
            {
                node->left = new TreeNode;
                node->left->item = key;
                node->left->left = NULL;
                node->left->right = NULL;
                done = true;
            }
        }
        else if(key.compare(node->item) > 0)
        {
            if(node->right != NULL)
            {
                node = node->right;
            }
            else
            {
                node->right = new TreeNode;
                node->right->item = key;
                node->right->left = NULL;
                node->right->right = NULL;
                done = true;
            }
        }
        else if(key.compare(node->item) == 0)
        {
            done = true;
        }
    }

}

it's becouse when you never change what was periviusly inserted, for example if you insert C at first the next item you insert(for example b) never can take place in root so if you insert "C","B","A" in this order you will have a tree shaped like :

    C
   /
  B
 /
A

you have to check every if the current node has to be changed! and reinsert you key couse your root may change at every insert! and the tree you draw would never generate the only pissible forms of trees your code generate are these for given inputs :

 ABC        ACB      BAC        CBA     CAB
                     BCA        
 A          A         B            C       C            
  \          \       / \          /       /      
   B          C     A   C        B       A            
    \        /                  /         \ 
     C      B                  A           B