title: Removing a node with two children in a Binary Tree
body: <p>So this is the code that I have so far.  I think I've got the logic down for the most part but I'm stuck on the part with two children.. I've figured out what sort of algorithm I have to use to make it work (I've annotated with comments at the bottom of the function), I'm just not sure how to start... Can anyone point me in the right direction??</p>
  
  <p>Heres what I have so far:</p>
  
  <pre><code>void BinaryTree::remove(int data){
  // Is the data valid?
  if(data &lt; 0){
      cerr &lt;&lt; data &lt;&lt; " is not valid.  Must be a positive integer value."  &lt;&lt; endl;
  }
  else{
      // Find the node
      BinNode* loc = root;
      BinNode* parent = nullptr;
      bool found = false;
      while(!found &amp;&amp; loc != nullptr){
          if(data &gt; loc-&gt;data){
              parent = loc;
              loc = loc-&gt;right;
          }
          else if(data &lt; loc-&gt;data){
              parent = loc;
              loc = loc-&gt;left;
          }
          else found = true;
      }
  
      // If there is a parent, take care of the pointer
      if(parent != nullptr){
          if(loc-&gt;data &lt; parent-&gt;data)
              parent-&gt;left = nullptr;
          else if(loc-&gt;data &gt; parent-&gt;data)
              parent-&gt;right = nullptr;
      }
      // If there are children, save pointers to them
      BinNode* leftChild = nullptr;
      BinNode* rightChild = nullptr;  
      if(loc-&gt;left != nullptr)
          leftChild = loc-&gt;left;
      if(loc-&gt;right != nullptr)
          rightChild = loc-&gt;right;
  
      // So now pointers to the children have been saved (if they exist) and
      // parent pointers have been taken care of (if they exist) the node can be deleted
      // If no children exist simply just delete the node and return
      delete loc;
      // If one child exists
      if(leftChild != nullptr || rightChild != nullptr){  
          if(leftChild != nullptr){
              if(leftChild-&gt;data &lt; parent-&gt;data)
                  parent-&gt;left = leftChild;
              else if(leftChild-&gt;data &gt; parent-&gt;data)
                  parent-&gt;right = leftChild;
          }
          else if(rightChild != nullptr){
              if(rightChild-&gt;data &lt; parent-&gt;data)
                  parent-&gt;left = rightChild;
              else if(rightChild-&gt;data &gt; parent-&gt;data)
                  parent-&gt;right = rightChild;
          }       
      }
  
      // Both children exist...this sucks.
      else if(leftChild != nullptr &amp;&amp; rightChild != nullptr){
          // Find a minimum in the right subtree
          BinNode * min = root;
          BinNode * minParent = nullptr;
          while(min-&gt;left != nullptr){
              minParent = min;
              min = min-&gt;left;
          }
          // Replace value of the node to be removed with the found minimum
          loc = new BinNode(min-&gt;data);
  
          // Delete the remaining duplicate node
          if(minParent != nullptr)
              minParent-&gt;left = nullptr;
          delete min;
      }
  }
  }
  </code></pre>