Remove fcn for Binary Search Tree
<p>Does this remove function for a Binary Search Tree look correct? When I try to delete a node, it runs and brings back the switch menu it's called from, but doesn't actually delete it when you reprint the tree. I'm not sure if I have a return out of place, possibly? </p>

<p>My question is: Does this remove statement actually remove the item passed, or does it just play around with it in a cruel fashion giving me a headache?</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;

       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
            // 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(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(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(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>
