title: Binary Search Tree in C: remove node function
body: <p>I'm putting together functions for a binary search tree and ran into a wall.  I'm working on each situation that might be encountered when a node holding a specified value needs to be removed from the tree.  I'm uncertain how to handle freeing the node if it does not have a left and right child.  The function must return a node. Do I back up, examine each left and right child, and remove the value while it's in a child?  But then if the value is in the root, wouldn't I have a similar problem with how to remove it?  Just by way of explanation, the program uses a void pointer then casts the TYPE val in a separate function compare() which evaluates both values and returns -1 for &lt;, 0 for ==, and 1 for >.</p>
  
  <pre><code>struct Node *_removeNode(struct Node *cur, TYPE val)
  {
      if (compare(cur-&gt;val, val) == 0) { //if val == cur-&gt;val
          if (cur-&gt;right != NULL &amp;&amp; cur-&gt;left != NULL) { //if cur has right and left
              cur = _leftMost(cur-&gt;right);
              free(_leftMost(cur-&gt;right));
          }
          else if (cur-&gt;right == NULL &amp;&amp; cur-&gt;left != NULL) {  //if cur has left
              cur = cur-&gt;left;
              free(cur-&gt;left);
          }
          else if (cur-&gt;right != NULL &amp;&amp; cur-&gt;left == NULL){ //if cur has right
              cur = cur-&gt;right;
              free(cur-&gt;right);
          }
          else if (cur-&gt;right == NULL &amp;&amp; cur-&gt;left == NULL){ //if cur has no child
                  //free cur if cur = val
  
          }
      }
      else if (compare(cur-&gt;val, val) == -1) {
          cur-&gt;right = _removeNode(cur-&gt;right, val);
      }
      else if (compare(cur-&gt;val, val) == 1) {
          cur-&gt;left = _removeNode(cur-&gt;left, val);
      }
  
      return cur;
  }
  </code></pre>