title: Binary Search Tree - Delete
body: <p>I am trying to write a program that takes in strings and places them in a binary search tree in alphabetical order once these are inserted into the tree, a user prompts for one word to be deleted, thus deleting that node from the tree, and then output the tree without that node back in order.</p>
  
  <p>Everything works for this up to the delete function, the delete function does work, but its very weird how it deletes.  I think currently it deletes a full side of the tree, because when I delete the last word, it typically works. I will upload my delete function and if more is needed I can upload the rest of my code.</p>
  
  <p>Thanks!</p>
  
  <pre><code>template&lt;typename T&gt; void Delete(TreeNode&lt;T&gt;*&amp; root, const T&amp; data)
  {
      if (root == NULL)
          return;
          if(data &lt; root-&gt;Value)
              return Delete(root-&gt;Left, data);
          else if (root-&gt;Value &gt; data)
              return Delete(root-&gt;Right, data);
          else
          {
              TreeNode&lt;T&gt;* old_root = root;
              if (root-&gt;Left == NULL)
              {
                  root = root-&gt;Right;
              }
              else if (root-&gt;Right == NULL)
              {
                  root = root-&gt;Left;
              }
              else
              {
                  replace_parent(old_root, old_root-&gt;Left);
              }
              delete old_root;
  
  
  
      }
  
  };
  
  template&lt;typename T&gt; void replace_parent(TreeNode&lt;T&gt;*&amp; old_root, TreeNode&lt;T&gt;*&amp; root)
  {
      if (root-&gt;Right != NULL)
      {
          replace_parent(old_root, root-&gt;Right);
      }
      else
      {
          old_root-&gt;Value = root-&gt;Value;
          old_root = root;
          root = root-&gt;Left;
      }
  };
  </code></pre>