title: Delete in Binary search tree in C
body: <p>I have implemented BST in C. Insert and lookup works fine. But delete has issues when deleting the root node. I'm not able to free the pointer to the root node. I could if I pass it as a double pointer, but I wanted to keep the code simple without using double pointers. Here I do NOT have a head pointer which points to the root node. Should I use a head pointer to the root node?</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  struct node
  {
      int data;
      struct node* left;
      struct node* right;
  };
  struct node* newNode(int data)
  {
      struct node* node = malloc(sizeof(struct node));
      node-&gt;data=data;
      node-&gt;left=NULL;
      node-&gt;right=NULL;
      return(node);
  }
  
  static int lookup(struct node* node,int target)
  {
      if(node==NULL)
      {
          return(0);
      }
      else
      {
          if(target == node-&gt;data)
          {
              return(1);
          }
          else
          {
              if(target &lt; node-&gt;data)
              {
                  return(lookup(node-&gt;left,target));
              }
              else
              {
                  return(lookup(node-&gt;right,target));
              }
          }
      }
  }
  
  
  struct node* insert(struct node* node, int data)
  {
      if(node==NULL)
      {
          return(newNode(data));
      }   
      else
      {
          if(data &lt; node-&gt;data)
          {
              node-&gt;left =insert(node-&gt;left,data);
          }
          else
          {
              node-&gt;right=insert(node-&gt;right,data);
          }
          return(node);
      }
  }
  
  struct node* delete(struct node* node, struct node* pnode, int target)
  {
      struct node* rchild;
      struct node* rchildparent;
      if(node==NULL)
      {
          return(pnode);
      }
      else
      {
          if(target == node-&gt;data)
          {
              if(node-&gt;left == NULL &amp;&amp; node-&gt;right == NULL) //leaf node
              {
                  if(pnode == NULL) //special case deleting the root node
                  {
                      free(node);
                      return(NULL);
                  }
                  if(pnode-&gt;left == node)
                  {
                      pnode-&gt;left = NULL;
                  }
                  else
                  {
                      pnode-&gt;right = NULL;
                  }
                  free(node);
                  return(pnode);
              }
              if(node-&gt;left ==NULL ) //one child
              {
                  if(pnode == NULL) //deleting root having no left child
                  {
                      struct node* temp = node;
                      node = node-&gt;right;
                      free(temp);
                      return(node);
                  }
                  if(pnode-&gt;left == node)
                  {
                      pnode-&gt;left = node-&gt;right;
                  }
                  else
                  {
                      pnode-&gt;right = node-&gt;right;
                  }   
                  free(node);
                  return(pnode);
              }
              if(node-&gt;right ==NULL ) //one child
              {
                  if(pnode == NULL) //deleting root having no right child
                  {
                      struct node* temp = node;
                      node = node-&gt;left;
                      free(temp);
                      return(node);
                  }
                  if(pnode-&gt;left == node)
                  {
                      pnode-&gt;left = node-&gt;left;
                  }
                  else
                  {
                      pnode-&gt;right = node-&gt;left;
                  }   
                  free(node);
                  return(pnode);
              }
  
              //two children case
              rchild = node-&gt;right;
              rchildparent=node;
              while(rchild-&gt;left != NULL)
              {
                  rchildparent=rchild;
                  rchild = rchild-&gt;left;
              }
              node-&gt;data=rchild-&gt;data;
              if(rchildparent == node)
              {
                  //rchildparent-&gt;right=rchild-&gt;right;
                  node-&gt;right=rchild-&gt;right;
              }
              else
              {
                  //rchildparent-&gt;left=NULL;
                  rchildparent-&gt;left=rchild-&gt;right;
              }
              free(rchild);
              if(pnode ==NULL) //root node
              {
                  return(node);
              }           
              return(pnode);
          }
          else
          {
              if(target &lt; node-&gt;data)
              {
                  delete(node-&gt;left,node,target);
                  return(node);
              }
              else
              {
                  delete(node-&gt;right,node,target);
                  return(node);
              }
          }
  
      }
  
  }
  void printinorder(struct node* node)
  {
      if(node == NULL)
      {
          return;
      }   
      printinorder(node-&gt;left);
      printf("%d\t",node-&gt;data);
      printinorder(node-&gt;right);
  }
  int main()
  {
      clock_t start,end;
      struct node* root = newNode(3);
      insert(root,7);
      insert(root,7);
      insert(root,7);
      printinorder(root);
      printf("\n");
      root = delete(root,NULL,6);
      printinorder(root);
      printf("\n");
  }
  </code></pre>
  
  <p>EDIT:
  Fixed the code as per @<code>modifiable lvalue</code> suggestion. Now is there a way I can improve the delete logic?</p>