title: Stuck at deleting node from Binary Search Tree
body: <p>I have been trying to follow the textbook &quot;Introduction to Algorithms&quot; but I'm stuck at the following step when deleting a node from a BST - when the node to be deleted has both children</p>
  <p>My code is below:</p>
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  #include &quot;bst.h&quot;
  
  
  void error()
  {
      fprintf(stderr, &quot;%s\n&quot;, &quot;Error assigning memory to node&quot;);
      exit(1);
  }
  
  void insert(node **root, int key)
  {
      node *t1, *t2;
  
      if (*root == NULL) {
          printf(&quot;Root is null\n&quot;);
          *root = (node *)malloc(sizeof(node));
          if (*root==NULL) {
              fprintf(stderr, &quot;%s\n&quot;, &quot;Cannot allocate memory for node in Insert&quot;);
              exit(1);
          }
          (*root)-&gt;key = key;
          (*root)-&gt;left = (*root)-&gt;right = NULL;
      }
      else {
          printf(&quot;Root contains data. Inserting new node.\n&quot;);
          t1 = *root;
  
          while (t1 != NULL) {
              t2 = t1;
  
              if (key &lt; t1-&gt;key)
                  t1 = t1-&gt;left;
              else
                  t1 = t1-&gt;right;
          }
  
          if(key &lt; t2-&gt;key) {
              t2-&gt;left = (node *) malloc(sizeof(node));
              t2 = t2-&gt;left;
              if (t2==NULL)
                  error();
              t2 -&gt; key = key;
          }
          else {
              t2-&gt;right = (node *) malloc(sizeof(node));
              t2 = t2-&gt;right;
              if (t2==NULL)
                  error();
              t2-&gt;key = key;
          }
      }
  
      
  }
  
  void inorder(node * root)
  {
      if (root!=NULL) {
          inorder(root-&gt;left);
          printf(&quot;%d -&gt;&quot;, root-&gt;key);
          inorder(root-&gt;right);
      }
  }
  
  node * search(node *root, int key)
  {
      node * t = root;
  
      while (t!=NULL)
      {
          if (key == t-&gt;key)
              return t;
          else if (key &lt; t-&gt;key)
              t = t-&gt;left;
          else
              t = t-&gt;right;
      }
      return NULL;
  }
  
  node * getparent(node * root, int key)
  {
      node * t = root, *parent = NULL;
  
      while (t!=NULL)
      {   
          if (key == t-&gt;key)
              return parent;
          else if (key &lt; t-&gt;key)
              t = t-&gt;left;
          else
              t = t-&gt;right;
          parent = t;
      }
      return NULL;
  }
  
  node * delete(node *root, int key)
  {
      node * todelete = search(root,key), *parent = getparent(root, key), *y;
      if (todelete==NULL) {
          fprintf(stderr, &quot;%s\n&quot;, &quot;Key not found&quot;);
          exit(2);
      }
  
      if (todelete-&gt;left == NULL &amp;&amp; todelete-&gt;right==NULL) { //Deleting node with no children
          if (todelete == parent-&gt;left)
              parent-&gt;left = NULL;
          else
              parent-&gt;right = NULL;
          free(todelete);
          return root;
      }
      else if (todelete-&gt;left &amp;&amp; !todelete-&gt;right) {
          if (todelete == parent-&gt;left)
              parent-&gt;left = todelete-&gt;left;
          else
              parent-&gt;right = todelete-&gt;right;
          free(todelete);
          return root;
      }
      else if (todelete-&gt;right &amp; !todelete-&gt;left) {
          if (todelete == parent-&gt;left)
              parent-&gt;left = todelete-&gt;left;
          else
              parent-&gt;right = todelete-&gt;right;
          free(todelete);
          return root;
      }
      else
      {
          node * yparent = NULL;
          y= todelete-&gt;right;
          while (y-&gt;left!=NULL)
          {
              y = y-&gt;left;
              yparent = y;
          }
          if(yparent != todelete) {
              //stuck here
          }
      }
  
  
  }
  </code></pre>
  <p>bst.h:</p>
  <pre><code>struct treenode
  {
      int key;
      struct treenode *left;
      struct treenode *right;
  };
  
  typedef struct treenode node;
  
  node * getparent(node * root, int key);
  void insert(node **root, int key);
  node * search(node *root, int key);
  node * delete(node *root, int key);
  void inorder(node * root);
  </code></pre>
  <p>Any guidance would be much appreciated. I should be trying to set the y = y-&gt;right and then set todelete-&gt;right = y correct?</p>