title: Deletion in Binary Search Tree for strings
body: <p>This program is a binary search tree of string to store information of students with the following details such as id, name and CGPA. And using unique id of a student to search, delete and insert different data. But in deletion when a subtree is involved the tree gets separated, I don't know what I'm doing wrong.</p>
  <pre><code>#include &lt;iostream&gt;
  using namespace std;
  
  struct BstNode
  {
      string iD;
      string name;
      float cgpa;
      BstNode *left;
      BstNode *right;
  };
  BstNode *root;
  BstNode *GetNewNode(string iD0, string n0, float cg0)
  {
      BstNode *NewNode = new BstNode();
      NewNode-&gt;iD = iD0;
      NewNode-&gt;name = n0;                                         
      NewNode-&gt;cgpa = cg0;
      NewNode-&gt;left = NULL;
      NewNode-&gt;right = NULL;
      return NewNode;
  }
  
  void PreOrder(BstNode *root)
  {
      if (root == NULL)
      {
          return;
      }
      cout &lt;&lt; &quot;ID: &quot; &lt;&lt; root-&gt;iD &lt;&lt; &quot;\nNAME: &quot; &lt;&lt; root-&gt;name &lt;&lt; &quot;\nCGPA: &quot; &lt;&lt; root-&gt;cgpa &lt;&lt; endl;
      PreOrder(root-&gt;left);
      PreOrder(root-&gt;right);
  }
  void InOrder(BstNode *root)
  {
      if (root == NULL)
      {
          return;
      }
      InOrder(root-&gt;left);
      cout &lt;&lt; &quot;ID: &quot; &lt;&lt; root-&gt;iD &lt;&lt; &quot;\nNAME: &quot; &lt;&lt; root-&gt;name &lt;&lt; &quot;\nCGPA: &quot; &lt;&lt; root-&gt;cgpa &lt;&lt; endl;
      InOrder(root-&gt;right);
  }
  void PostOrder(BstNode *root)
  {
      if (root == NULL)
      {
          return;
      }
      PostOrder(root-&gt;left);
      PostOrder(root-&gt;right);
      cout &lt;&lt; &quot;ID: &quot; &lt;&lt; root-&gt;iD &lt;&lt; &quot;\nNAME: &quot; &lt;&lt; root-&gt;name &lt;&lt; &quot;\nCGPA: &quot; &lt;&lt; root-&gt;cgpa &lt;&lt; endl;
      cout &lt;&lt; endl;
  }
  BstNode *Insert(BstNode *root, string iD2, string n2, float cg2)
  {
      if (root == NULL)
      {
          root = GetNewNode(iD2, n2, cg2);
      }
      else if (iD2 &lt;= root-&gt;iD)
      {
          root-&gt;left = Insert(root-&gt;left, iD2, n2, cg2);
      }
      else
      {
          root-&gt;right = Insert(root-&gt;right, iD2, n2, cg2);
      }
      return root;
  }
  
  BstNode *Rectify(BstNode *root, string id1, string n, float cg)
  {
      root-&gt;iD = id1;
      root-&gt;name = n;
      root-&gt;cgpa = cg;
      return root;
  }
  struct BstNode *FindMin(BstNode *root)
  {
      struct BstNode* current = root;
   
      /* loop down to find the leftmost leaf */
      while (current &amp;&amp; current-&gt;left != NULL)
          current = current-&gt;left;
   
      return current;
  }
  
  BstNode *Delete(BstNode *root, string data)
  {
      if (root == NULL)
          return root;
      else
      {
          if (data &lt; root-&gt;iD)
              root-&gt;left = Delete(root-&gt;left, data);
  
          else if (data &gt; root-&gt;iD)
              root-&gt;right = Delete(root-&gt;right, data);
          else
          {
              if (root-&gt;left == NULL and root-&gt;right == NULL)
                  return NULL;
  
              else if (root-&gt;left == NULL)
              {
                 struct BstNode *temp = root-&gt;right;
                  delete(root);
                  return temp;
              }
              else if (root-&gt;right == NULL)
              {
                 struct BstNode *temp = root-&gt;left;
                  delete(root);
                  return temp;
              }
              else
              {
                 struct BstNode *temp = FindMin(root-&gt;right);
                  root-&gt;iD = temp-&gt;iD;
                  root-&gt;name = temp-&gt;name;
                  root-&gt;cgpa = temp-&gt;cgpa;
                  root-&gt;right = Delete(root-&gt;right, temp-&gt;iD);
              }
          }
          return root;
      }
  }
  
      BstNode *Search(BstNode * root, string iDs)
      {
          cout &lt;&lt; &quot;Finding &quot; &lt;&lt; endl;
          if (root == NULL)
          {
              cout &lt;&lt; &quot;No such info!&quot; &lt;&lt; endl;
              return root;
          }
          else if (root-&gt;iD == iDs)
          {
              cout &lt;&lt; &quot;Found 0 &quot; &lt;&lt; endl;
              cout &lt;&lt; &quot;ID: &quot; &lt;&lt; root-&gt;iD &lt;&lt; endl;
              cout &lt;&lt; &quot;NAME: &quot; &lt;&lt; root-&gt;name &lt;&lt; endl;
              cout &lt;&lt; &quot;CGPA: &quot; &lt;&lt; root-&gt;cgpa &lt;&lt; endl;
              bool done = false;
              while (!done)
              {
                  cout &lt;&lt; &quot;Would you like to update this student's information? [y/n]\n&quot;;
                  string x;
                  cin &gt;&gt; x;
                  if (x == &quot;y&quot;)
                  {
                      cout &lt;&lt; &quot;The following fields are updatable:\n&quot;;
                      cout &lt;&lt; &quot;1. Student ID\n&quot;;
                      cout &lt;&lt; &quot;2. Student Name\n&quot;;
                      cout &lt;&lt; &quot;3. Student CGPA\n&quot;;
                      cout &lt;&lt; &quot;4. Remove Student\n&quot;;
                      cout &lt;&lt; &quot;Enter your choice:\n&quot;;
                      bool done1 = false;
                      while (!done1)
                      {
                          int ch;
                          cin &gt;&gt; ch;
                          if (ch == 1)
                          {
                              cout &lt;&lt; &quot;Please enter new ID:   \n&quot;;
                              string nwid;
                              cin &gt;&gt; nwid;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; &quot;Updating  \n&quot;;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              root = Rectify(root, nwid, root-&gt;name, root-&gt;cgpa);
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; &quot;Updated Successfully!  \n&quot;;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; root-&gt;iD &lt;&lt; endl;
                              cout &lt;&lt; root-&gt;name &lt;&lt; endl;
                              cout &lt;&lt; root-&gt;cgpa &lt;&lt; endl;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              done1 = true;
                          }
                          else if (ch == 2)
                          {
                              cout &lt;&lt; &quot;Please enter new name:   \n&quot;;
                              string nwname;
                              cin &gt;&gt; nwname;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; &quot;Updating  \n&quot;;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              root = Rectify(root, root-&gt;iD, nwname, root-&gt;cgpa);
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; &quot;Updated Successfully!  \n&quot;;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; root-&gt;iD &lt;&lt; endl;
                              cout &lt;&lt; root-&gt;name &lt;&lt; endl;
                              cout &lt;&lt; root-&gt;cgpa &lt;&lt; endl;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              done1 = true;
                          }
                          else if (ch == 3)
                          {
                              cout &lt;&lt; &quot;Please enter new CGPA:   \n&quot;;
                              float nwcg;
                              cin &gt;&gt; nwcg;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; &quot;Updating  \n&quot;;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              root = Rectify(root, root-&gt;iD, root-&gt;name, nwcg);
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; &quot;Updated Successfully!  \n&quot;;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              cout &lt;&lt; root-&gt;iD &lt;&lt; endl;
                              cout &lt;&lt; root-&gt;name &lt;&lt; endl;
                              cout &lt;&lt; root-&gt;cgpa &lt;&lt; endl;
                              cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
                              done1 = true;
                          }
                          else if (ch == 4)
                          {
                              cout &lt;&lt; &quot;Removing\n&quot;;
                             root = Delete(root, root-&gt;iD);
                              cout &lt;&lt; &quot;Removed!\n&quot;;
                              return root;
                              done1 = true;
                          }
                          else
                          {
                              cout &lt;&lt; &quot;Wrong input try again!  \n&quot;;
                          }
                      }
                      done = true;
                  }
                  else if (x == &quot;n&quot;)
                  {
                      done = true;
                  }
                  else
                  {
                      cout &lt;&lt; &quot;Wrong input try again!  \n&quot;;
                  }
              }
  
              return root;
          }
          else if (iDs &lt;= root-&gt;iD)
          {
              return Search(root-&gt;left, iDs);
          }
          else
          {
              return Search(root-&gt;right, iDs);
          }
      }
  
      int main()
      {
          root = NULL;
          root = Insert(root, &quot;21-44631-1&quot;, &quot;Rafiul&quot;, 3.75);
          root = Insert(root, &quot;21-44531-1&quot;, &quot;Haque&quot;, 4.0);
          root = Insert(root, &quot;21-44431-1&quot;, &quot;Rafsun&quot;, 3.78);
          root = Insert(root, &quot;21-44331-1&quot;, &quot;Rafi&quot;, 3.5);
          root = Insert(root, &quot;21-44231-1&quot;, &quot;ABC&quot;, 4.0);
          root = Insert(root, &quot;21-44611-1&quot;, &quot;AC&quot;, 4.0);
          cout &lt;&lt; &quot;Please enter the ID you want to search: &quot;;
          string s;
          cin &gt;&gt; s;
          cout &lt;&lt; endl;
          Search(root, s);
          cout &lt;&lt; &quot;Reading tree in preorder : \n&quot;;
          PreOrder(root);
          cout&lt;&lt;&quot;============================&quot;&lt;&lt; endl;
          cout &lt;&lt; &quot;\nReading tree in inorder : \n&quot;;
          InOrder(root);
          cout&lt;&lt;&quot;============================&quot;&lt;&lt; endl;
          cout &lt;&lt; &quot;\nReading tree in postorder : \n&quot;;
          PostOrder(root);
          cout &lt;&lt; &quot;============================&quot; &lt;&lt; endl;
      }
  </code></pre>