title: BST code is not working with large number
body: <p>I have a very frustrated situation with my BST code:</p>
  
  <pre><code>vector&lt;int&gt; order;
  BinarySearchTree tree;
  for (int i=0; i&lt;1000; ++i) {
    int j = rand()%1000;
    order.push_back(j);
  }
  for (int i = 0; i &lt; 1000; ++i) {
    tree.insert(order[i]);
  }
  while(!tree.isEmpty()) {
    cout &lt;&lt; tree.min() &lt;&lt; endl;
    tree.remove(tree.min());
  }
  </code></pre>
  
  <p>the code is working perfectly fine with small number of i, say 10, or 100. However, it is stop working when i is 1000. </p>
  
  <p>the insert function is as follows</p>
  
  <pre><code>void BinarySearchTree::insert(int d)
  {
    tree_node* t = new tree_node;
    tree_node* parent;
    t-&gt;data = d;
    t-&gt;left = NULL;
    t-&gt;right = NULL;
    parent = NULL;
  
    // is this a new tree?
    if(isEmpty()) root = t;
    else
    {
      //Note: ALL insertions are as leaf nodes
      tree_node* curr;
      curr = root;
      // Find the Node's parent
      while(curr)
      {
        parent = curr;
        if(t-&gt;data &gt; curr-&gt;data) curr = curr-&gt;right;
        else curr = curr-&gt;left;
      }
  
      if(t-&gt;data &lt;= parent-&gt;data)
        parent-&gt;left = t;
      else
        parent-&gt;right = t;
    }
  }
  </code></pre>
  
  <p>In response to the comments, i am going to post all the code. :)</p>
  
  <pre><code>void BinarySearchTree::remove(int d)
  {
    //Locate the element
    bool found = false;
    if(isEmpty())
    {
      cout&lt;&lt;" This Tree is empty! "&lt;&lt;endl;
      return;
    }
  
    tree_node* curr;
    tree_node* parent;
    curr = root;
    //parent = root;
  
    while(curr != NULL)
    {
      if(curr-&gt;data == d)
      {
        found = true;
        break;
      }
      else
      {
        parent = curr;
        if(d&gt;curr-&gt;data) curr = curr-&gt;right;
        else curr = curr-&gt;left;
      }
    }
    if(!found)
    {
      cout&lt;&lt;" Data not found! "&lt;&lt;endl;
      return;
    }
  
  
    // 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children
  
    // Node with single child
    if((curr-&gt;left == NULL &amp;&amp; curr-&gt;right != NULL)|| (curr-&gt;left != NULL
      &amp;&amp; curr-&gt;right == NULL))
    {
      if(curr-&gt;left == NULL &amp;&amp; curr-&gt;right != NULL)
      {
        if (curr == root) {
          root = curr-&gt;right;
          delete curr;
        }
        else {
          if(parent-&gt;left == curr)
          {
            parent-&gt;left = curr-&gt;right;
            delete curr;
          }
          else
          {
            parent-&gt;right = curr-&gt;right;
            delete curr;
          }
        }
      }
      else // left child present, no right child
      {
        if (curr==root) {
          root = curr-&gt;left;
          delete curr;
        }
        else {
          if(parent-&gt;left == curr)
          {
            parent-&gt;left = curr-&gt;left;
            delete curr;
          }
          else
          {
            parent-&gt;right = curr-&gt;left;
            delete curr;
          }
        }
      }
      return;
    }
  
    //We're looking at a leaf node
    if( curr-&gt;left == NULL &amp;&amp; curr-&gt;right == NULL)
    {
      if (curr == root) {
        root = NULL;
        delete curr;
        return;
      }
      else {
        if(parent-&gt;left == curr) parent-&gt;left = NULL;
        else parent-&gt;right = NULL;
        delete curr;
        return;
      }
    }
  
  
    //Node with 2 children
    // replace node with smallest value in right subtree
    if (curr-&gt;left != NULL &amp;&amp; curr-&gt;right != NULL)
    {
      tree_node* chkr;
      chkr = curr-&gt;right;
      if((chkr-&gt;left == NULL) &amp;&amp; (chkr-&gt;right == NULL))
      {
        curr = chkr;
        delete chkr;
        curr-&gt;right = NULL;
      }
      else // right child has children
      {
        //if the node's right child has a left child
        // Move all the way down left to locate smallest element
  
        if((curr-&gt;right)-&gt;left != NULL)
        {
          tree_node* lcurr;
          tree_node* lcurrp;
          lcurrp = curr-&gt;right;
          lcurr = (curr-&gt;right)-&gt;left;
          while(lcurr-&gt;left != NULL)
          {
            lcurrp = lcurr;
            lcurr = lcurr-&gt;left;
          }
          curr-&gt;data = lcurr-&gt;data;
          delete lcurr;
          lcurrp-&gt;left = NULL;
        }
        else
        {
          tree_node* tmp;
          tmp = curr-&gt;right;
          curr-&gt;data = tmp-&gt;data;
          curr-&gt;right = tmp-&gt;right;
          delete tmp;
        }
  
      }
      return;
    }
  
  }
  </code></pre>
  
  <p>and the min() function</p>
  
  <pre><code>int BinarySearchTree::min()
  {
    tree_node *p=root;
    while (p-&gt;left != NULL)
      p=p-&gt;left;
    return (p-&gt;data);
  }
  </code></pre>