title: Implementing a deletion function for a binary search tree in C
body: <p>I've been trying to implement a function in C that deletes a node in a binary tree that should (theoretically) take care of three all cases, i.e.:</p>
  
  <ul>
  <li>Node is a leaf</li>
  <li>Node has one child</li>
  <li>Node has two children</li>
  </ul>
  
  <p>Is there a way to handle the whole deletion function without checking separately each case? As a commenter below noted I do check for a lot of cases and perhaps the whole problem can be addressed recursively by checking for one fundamental case.</p>
  
  <p>I'm particularly interested in the case where I delete a node within the tree that has a parent and itself is a parent of two children nodes.</p>
  
  <p>Both answers below have been useful but I don't think they address the problem in its entirety.</p>
  
  <p>Here's what I have:</p>
  
  <pre><code>typedef struct Node
  {
      int key;
      int data;
      struct Node *left;
      struct Node *right;
      struct Node *parent;
  } Node;
  
  /* functions that take care of inserting and finding a node and also traversing and freeing the tree */
  ...
  
  void delete(Node *root, int key)
  {
      Node *target = find(root, key); // find will return the node to be deleted
  
      Node *parent = target-&gt;parent; // parent of node to be deleted
  
      // no children
      if (target-&gt;left == NULL &amp;&amp; target-&gt;right == NULL)
      {
          // is it a right child
          if (target-&gt;key &gt; parent-&gt;key)
              parent-&gt;right = NULL;
          // must be a left child
          else
              parent-&gt;left = NULL;
  
          free(target);
      }
  
      // one child
      else if ((target-&gt;left == NULL &amp;&amp; target-&gt;right != NULL) || (target-&gt;left != NULL &amp;&amp; target-&gt;right == NULL))
      {
          // here we swap the target and the child of that target, then delete the target
          Node *child = (target-&gt;left == NULL) ? target-&gt;right : target-&gt;left;
          child-&gt;parent = parent;
          if (parent-&gt;left == target) parent-&gt;left = child;
          else if (parent-&gt;right == target) parent-&gt;right = child;
          free(target);
      }
      // two children
        else
      {
  
          // find the largest node in the left subtree, this will be the node
          // that will take the place of the node to be deleted
          Node *toBeRepl = max(target-&gt;left);
  
          // assign the data of the second largest node
          target-&gt;key   = toBeRepl-&gt;key;
          target-&gt;data  = toBeRepl-&gt;data;
  
          // if new node immediately to the left of target 
          if (toBeRepl == target-&gt;left)
          {   
              target-&gt;left  = toBeRepl-&gt;left;
              Node *newLeft = target-&gt;left;
              if (newLeft != NULL) newLeft-&gt;parent = target;
          }
          else
          {
              delete(target-&gt;left, toBeRepl-&gt;key);
              // Node *replParent = toBeRepl-&gt;parent;
              // replParent-&gt;right = NULL;
          }
  }
  </code></pre>
  
  <p>I would greatly appreciate your feedback.</p>
  
  <p>edit: Just to clarify, I'm trying to delete a particular node without touching its subtrees (if there are any). They should remain intact (which I've handled by swapping the values of the node to be deleted and (depending on the case) one of the nodes of its substrees).</p>
  
  <p>edit: I've used as a reference the following wikipedia article:
  <a href="http://en.wikipedia.org/wiki/Binary_search_tree#Deletion" rel="nofollow">http://en.wikipedia.org/wiki/Binary_search_tree#Deletion</a><br>
  Which is where I got the idea for swapping the nodes values in case of two children, particularly the quote:</p>
  
  <blockquote>
    <p>Call the node to be deleted N. Do not delete N. Instead, choose either
    its in-order successor node or its in-order predecessor node, R.
    Replace the value of N with the value of R, then delete R.</p>
  </blockquote>
  
  <p>There is some interesting code in C++ there for the above case, however I'm not sure how exactly the swap happens:</p>
  
  <pre><code>else    //2 children
  {
          temp = ptr-&gt;RightChild;
          Node&lt;T&gt; *parent = nullptr;
  
          while(temp-&gt;LeftChild!=nullptr)
          {
                  parent = temp;
                  temp = temp-&gt;LeftChild;
          }
          ptr-&gt;data = temp-&gt;data;
          if (parent!=nullptr)
                  Delete(temp,temp-&gt;data);
          else
                  Delete(ptr-&gt;rightChild,ptr-&gt;RightChild-&gt;data);
  }
  </code></pre>
  
  <p>Could somebody please explain what's going on in that section? I'm assuming that the recursion is of a similar approach as to the users comments' here.</p>