title: How to properly insert/delete in a binary search tree in C?
body: <p>I kinda have to put my previous C questions on hold cause this one is more important now...</p>
  
  <p>I have already coded the insert and delete functions on my binary search tree but the delete function is incomplete. There's a couple of things I need help in...</p>
  
  <p><strong>1)</strong> Is my insert function good or can it be improved somehow?</p>
  
  <p><strong>2)</strong> My delete function lacks the deletion of a node with both the left and right childs. I've searched a lot in the past few hours but couldn't find a proper way to do it.</p>
  
  <p><strong>2.a)</strong> How should I delete a node with 2 child nodes?</p>
  
  <p><strong>2.b)</strong> As in the first question, is the delete function good or can it be improved? This one I know it can because I'm repeating lots of code in those ifs but I don't see how can I improve it, I need help on that too.</p>
  
  <pre><code>typedef struct sClientProfile *ClientProfile;
  typedef struct sClientTree *ClientTree;
  
  typedef struct sClientProfile {
      char *clientName;
      int clientAge;
      int clientNIF;
  } nClientProfile;
  
  typedef struct sClientTree {
      ClientProfile clientProfile;
      char *clientName;
  
      ClientTree leftTree;
      ClientTree rightTree;
  } nClientTree;
  
  void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
      if(!*cTree) {
          ClientTree new = (ClientTree)malloc(sizeof(nClientTree));
  
          if(!new) {
              perror("malloc");
          }
  
          new-&gt;clientName = strdup(cProfile-&gt;clientName);
          new-&gt;clientProfile = cProfile;
  
          new-&gt;leftTree = NULL;
          new-&gt;rightTree = NULL;
  
          *cTree = new;
      } else {
          if(strcmp((*cTree)-&gt;clientName, cProfile-&gt;clientName) &gt; 0) {
              addClientToTree(&amp;(*cTree)-&gt;leftTree, cProfile);
          } else {
              addClientToTree(&amp;(*cTree)-&gt;rightTree, cProfile);
          }
      }
  }
  
  void deleteClientFromTree(ClientTree *cTree, char *cName) {
      if(!cTree) return;
  
      int nCompare = strcmp((*cTree)-&gt;clientName, cName);
  
      if(nCompare &gt; 0) {
          deleteClientFromTree(&amp;(*cTree)-&gt;leftTree, cName);
      } else if(nCompare &lt; 0) {
          deleteClientFromTree(&amp;(*cTree)-&gt;rightTree, cName);
      } else {
          if(!(*cTree)-&gt;leftTree &amp;&amp; !(*cTree)-&gt;rightTree) {
              ClientTree cliPtr = *cTree;
  
              free(cliPtr-&gt;clientProfile);
              free(cliPtr);
  
              cliPtr-&gt;clientProfile = NULL;
              cliPtr = NULL;
  
              *cTree = NULL;
          } else if(!(*cTree)-&gt;leftTree) {
              ClientTree cliPtr = *cTree;
  
              free(cliPtr-&gt;clientProfile);
              free(cliPtr);
  
              cliPtr-&gt;clientProfile = NULL;
  
              *cTree = (*cTree)-&gt;rightTree;
          } else if(!(*cTree)-&gt;rightTree) {
              ClientTree cliPtr = *cTree;
  
              free(cliPtr-&gt;clientProfile);
              free(cliPtr);
  
              cliPtr-&gt;clientProfile = NULL;
  
              *cTree = (*cTree)-&gt;leftTree;
          } else {
  
              // MISSING DELETE CASE
  
          }
      }
  }
  </code></pre>
  
  <p>You'll probably notice but let me just make 2 remarks:</p>
  
  <ul>
  <li>This tree uses strings instead of the normal int representation. That's why I use strcmp() all the way, I think I'm using it right.</li>
  <li>I'm not using recursion, I rather pass the pointer (of a structure pointer in this case) and work with that. It looks more clean somehow and in the future I want to return a success value if a node was deleted.</li>
  </ul>
  
  <p><strong>UPDATE BELOW:</strong><br>
  I've already did my iterative version of the delete function but I don't like some things about it, maybe they can be improved (or not) but I can't see how. I've also tried to code the case it was missing, deleting a node with 2 childs, but it's not working as it should...</p>
  
  <p>I've commented the whole code where I think the code can be improved and where's the problem. I've also named those problems as A, B (there's no B anymore), C and D so we can reference to them easily.</p>
  
  <pre><code>bool deleteClientFromTree(ClientTree *cTree, char *cName) {
      if(!cTree) return FALSE;
  
      ClientTree currPtr = *cTree;
      ClientTree prevPtr = NULL;
      int nCompare;
  
      while(currPtr) {
          nCompare = strcmp(currPtr-&gt;clientName, cName);
  
          if(nCompare &gt; 0) {
              prevPtr = currPtr;
              currPtr = currPtr-&gt;leftTree;
          } else if(nCompare &lt; 0) {
              prevPtr = currPtr;
              currPtr = currPtr-&gt;rightTree;
          } else {
              /*
               * A)
               * 
               * The following cases have 3 lines in common, the free()
               * calls and return statement. Is there anyway to improve
               * this code and make it more compact?
               * 
               * Of course, the printf's are to be removed...
               */
              if(!prevPtr &amp;&amp; !currPtr-&gt;leftTree &amp;&amp; !currPtr-&gt;rightTree) {
                  printf("CASE #1\n");
  
                  *cTree = NULL;
  
                  free(currPtr-&gt;clientProfile);
                  free(currPtr);
  
                  return TRUE;
              } else if(!currPtr-&gt;leftTree || !currPtr-&gt;rightTree) {
                  printf("CASE #2\n");
  
                  if(prevPtr-&gt;leftTree == currPtr) {
                      prevPtr-&gt;leftTree = currPtr-&gt;rightTree;
                  } else {
                      prevPtr-&gt;rightTree = currPtr-&gt;leftTree;
                  }
  
                  free(currPtr-&gt;clientProfile);
                  free(currPtr);
  
                  return TRUE;
              } else {
                  printf("CASE #3\n");
  
                  ClientTree tempPtr = currPtr-&gt;rightTree;
  
                  while(tempPtr-&gt;leftTree) {
                      tempPtr = tempPtr-&gt;leftTree;
                  }
  
                  /*
                   * C)
                   * 
                   * This has a big problem...
                   * 
                   * If you take a look at the ClientProfile structure,
                   * in the first post, you'll see two ints
                   * (clientNIF/clientAge) and one char* (clientName).
                   * 
                   * The problem is that the following code line is only
                   * copying the integer data, not the string. For some
                   * reason, the string remains the old one.
                   * 
                   * I tried to use strdup() directly on clientName like:
                   * currPtr-&gt;clientProfile-&gt;clientName = strdup(tempPtr-&gt;clientProfile-&gt;clientName);
                   * but it still doesn't work.
                   * 
                   * Why everything is being copied but the strings?
                   */
                  currPtr-&gt;clientProfile = tempPtr-&gt;clientProfile;
  
                  /*
                   * D)
                   * 
                   * Is there anyway to not call the function itself
                   * and make the while loop once again and delete the
                   * corresponding leaf?
                   */
                  return deleteClientFromTree(&amp;currPtr-&gt;rightTree, tempPtr-&gt;clientProfile-&gt;clientName);
              }
          }
      }
  
      return FALSE;
  }
  </code></pre>