title: Binary Search Tree. Insert method inserting incorrectly
body: <p>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. </p>
  
  <p>A, B, C</p>
  
  <p>I should have</p>
  
  <pre><code>   B
    /  \
   A    C
  </code></pre>
  
  <p>but somehow I end up with like:</p>
  
  <pre><code>   C
    / \
   B   A
  </code></pre>
  
  <p>or something different depending in which order I insert in my tree.</p>
  
  <p>This is my tree class:</p>
  
  <p>This is my insert method and insert helper method. Can you take a look and see what I'm doing wrong? Thanks in advance.</p>
  
  <pre><code>void BinarySortTree::insert(string key)
  {
      if(root != NULL)
      {
          insert(key, root);
      }
      else
      {
          root = new TreeNode;
          root-&gt;item = key;
          root-&gt;left = NULL;
          root-&gt;right = NULL;
      }
  }
  
  void BinarySortTree::insert(string key, TreeNode *node)
  {
      bool done = false;
  
      while(!done)
      {
          if(key.compare(node-&gt;item) &lt; 0)
          {
              if(node-&gt;left != NULL)
              {
                  node = node-&gt;left;
              }
              else
              {
                  node-&gt;left = new TreeNode;
                  node-&gt;left-&gt;item = key;
                  node-&gt;left-&gt;left = NULL;
                  node-&gt;left-&gt;right = NULL;
                  done = true;
              }
          }
          else if(key.compare(node-&gt;item) &gt; 0)
          {
              if(node-&gt;right != NULL)
              {
                  node = node-&gt;right;
              }
              else
              {
                  node-&gt;right = new TreeNode;
                  node-&gt;right-&gt;item = key;
                  node-&gt;right-&gt;left = NULL;
                  node-&gt;right-&gt;right = NULL;
                  done = true;
              }
          }
          else if(key.compare(node-&gt;item) == 0)
          {
              done = true;
          }
      }
  
  }
  </code></pre>