title: Deleting Root Node of a Binary Search Tree
body: <p>I have this function for deleting a node in a binary search tree which seems to be working EXCEPT in the case where I ask it to delete the root node. It is supposed to take the  right-most value on the left and replace the node with that; however, once that happens, the new root node's children pointers don't seem to point to the original root node's children. Code is as follows:</p>
  
  <pre><code>bool delete_node(Node*&amp; root, TYPE data) {
  Node* toDelete;
  Node* parent;
  
  // This function is defined appropriately elsewhere, and finds the target to be deleted
  toDelete = find(data, root);
  
  if (!toDelete) {
      return false;
  }
  
  // This function is defined appropriately elsewhere, and finds the parent of the node to be deleted
  parent = find_parent(root, toDelete);
  
  // Other cases left out because they work
  // If the target node has two children:
  if (toDelete-&gt;left &amp;&amp; toDelete-&gt;right) 
  {
  
      // find rightmost child on left that is a leaf
      Node *replacement = toDelete-&gt;left;
      while (replacement-&gt;right) 
      {
          replacement = replacement-&gt;right;
      }
  
      // set the target node's data
      toDelete-&gt;data = replacement-&gt;data;
      if (parent) 
      {
          if ( parent-&gt;data &lt; toDelete-&gt;data ) 
          {
              parent-&gt;right = replacement;
          } else
          {
              parent-&gt;left = replacement;
          }
      } else 
      {
          // if node has no parents, then it is the root and should be replaced with replacement
          // This line here is what seems to be causing my trouble...I think
          root = replacement;
      }
      parent = find_parent(toDelete, replacement);
      if (parent) 
      {
          if (parent-&gt;left == replacement)
              parent-&gt;left = NULL;
          else
              parent-&gt;right = NULL;
      }
      delete toDelete;
      return true; 
  }
  }
  </code></pre>
  
  <p>Thanks in advance!</p>