title: delete node in BBST
body: <p>Deletion of node (value 8 or 2) does not work. Rest entire code works fine. Even delete node 4 works. I am not able to understand the problem. </p>
  
  <p>Code: In the main() function, I created a balanced-binary-search-tree from a 1D-vector.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  
  
  using namespace std;
  
  class TNode
  {
  public:
      TNode(){}
      ~TNode(){ std::cout &lt;&lt;"TNode destroyed" &lt;&lt; endl; }
      TNode *left;
      TNode *right;
      int data;
  };
  
  ////////////////////////////////////////////////////////////////////
  //////////////////////////   TREE   ////////////////////////////////
  ////////////////////////////////////////////////////////////////////
  class TREE
  {
  public:
      TREE(){}
      ~TREE(){}
      TNode* createBBST(std::vector&lt;int&gt;&amp; arr, int startIdx, int endIdx);
      void preOrderTraverseBT(TNode *node);
      void inOrderTraverseBT(TNode *node);
      void postOrderTraverseBT(TNode *node);
      TNode* searchBBST(TNode *rootnode, int data);
      TNode* insertBBST(TNode *rootnode, int data);
      void deleteBBST(TNode *rootnode, int data);
      TNode* findPred(TNode *rootnode);
  };
  
  TNode* TREE::createBBST(std::vector&lt;int&gt;&amp; arr, int startIdx, int endIdx)
  {
      //base-case
      if(startIdx&gt;endIdx)
          return NULL;
  
      /* Get the middle element and make it root */
      TNode *root = new TNode;
      int mid = (startIdx+endIdx)/2;
      root-&gt;data = arr[mid];
  
      /* Recursively construct the left subtree and make it left child of root */
      root-&gt;left = createBBST(arr, startIdx, mid-1);
  
      /* Recursively construct the right subtree and make it right child of root */
      root-&gt;right = createBBST(arr, mid+1, endIdx);
  
      return root;
  }
  
  void TREE::preOrderTraverseBT(TNode *node)
  {
  
      if(node==NULL)
          return;
      cout &lt;&lt; node-&gt;data &lt;&lt; " ";
      preOrderTraverseBT(node-&gt;left);
      preOrderTraverseBT(node-&gt;right);
  
      return;
  }
  
  void TREE::inOrderTraverseBT(TNode *node)
  {
  
      if(node==NULL)
          return;
  
      inOrderTraverseBT(node-&gt;left);
      cout &lt;&lt; node-&gt;data &lt;&lt; " ";
      inOrderTraverseBT(node-&gt;right);
  
      return;
  }
  
  
  
  TNode* TREE::searchBBST(TNode *rootnode, int data)
  {
      if(rootnode==NULL)
          return NULL;    
  
      if(rootnode-&gt;data == data)
          return rootnode;
      else if(rootnode-&gt;data &gt; data){
          return searchBBST(rootnode-&gt;left, data);
      }
      else //if(rootnode-&gt;data &lt; data)
          return searchBBST(rootnode-&gt;right, data);   
  }
  
  TNode* TREE::insertBBST(TNode *rootnode, int data)
  {   
  
      if(rootnode-&gt;data &gt;= data)
      {
          if(rootnode-&gt;left==NULL)
          {
              rootnode-&gt;left = new TNode;
              rootnode-&gt;left-&gt;left=NULL; rootnode-&gt;left-&gt;right=NULL;
              rootnode-&gt;left-&gt;data = data;
              return rootnode-&gt;left;
          }
          else// if(rootnode-&gt;left!=NULL)
          {
              return insertBBST(rootnode-&gt;left, data);
          }       
      }
      else// if(rootnode-&gt;data &lt; data)
      {
          if(rootnode-&gt;right==NULL)
          {
              rootnode-&gt;right = new TNode;
              rootnode-&gt;right-&gt;left=NULL; rootnode-&gt;right-&gt;right=NULL;
              rootnode-&gt;right-&gt;data = data;
              return rootnode-&gt;right;
          }
          else// if(rootnode-&gt;right!=NULL)
          {
              return insertBBST(rootnode-&gt;right, data);
          }   
      }
  
      //
  }
  
  TNode* TREE::findPred(TNode *rootnode)
  {
      if(rootnode==NULL)
          return rootnode;
  
      return findPred(rootnode-&gt;right);
  }
  
  void TREE::deleteBBST(TNode *rootnode, int data)
  {
      cout &lt;&lt; "Delete node : " &lt;&lt; data  &lt;&lt; endl;
  
      TNode *deletenode = searchBBST(rootnode, data);
  
      TNode* temp = NULL;
      if(deletenode-&gt;left==NULL &amp;&amp; deletenode-&gt;right==NULL) /* 0 Child */
      {
          cout &lt;&lt; "0 child..." &lt;&lt; endl;
  
          delete deletenode;
          deletenode = NULL;
  
          inOrderTraverseBT( rootnode );
          cout &lt;&lt; "\ndeleted..."&lt;&lt;endl;
      }
      else if(deletenode-&gt;left!=NULL &amp;&amp; deletenode-&gt;right==NULL) /* 1 Child */
      {
          cout &lt;&lt; "1 child..." &lt;&lt; endl;
          //copy left child to its parent
          temp = deletenode-&gt;left;
          deletenode-&gt;data = temp-&gt;data;
          deletenode-&gt;left = temp-&gt;left;
          deletenode-&gt;right = temp-&gt;right;
  
      }
      else if(deletenode-&gt;left==NULL &amp;&amp; deletenode-&gt;right!=NULL) /* 1 Child */
      {
          cout &lt;&lt; "1 child..." &lt;&lt; endl;
          temp = deletenode-&gt;right;
          deletenode-&gt;data = temp-&gt;data;
          deletenode-&gt;right = temp-&gt;right;    
          deletenode-&gt;left = temp-&gt;left;          
      }
      else /* 2 Children */
      {
          cout &lt;&lt; "2 child..." &lt;&lt; endl;
          //find predecessor
          TNode* pred = findPred(deletenode-&gt;left);
  
          //if pred has no child
          if(pred-&gt;left == NULL)
          {
              deletenode-&gt;data = pred-&gt;data;
          }
          else
          {
              //if pred has a left child
              deletenode-&gt;data = pred-&gt;data;
              pred-&gt;data = pred-&gt;left-&gt;data;
              pred-&gt;left = pred-&gt;left-&gt;left;
          }
  
          delete pred;
          pred = NULL;
      }
  
      //delete the old left child
      delete temp;
      temp = NULL;
  }
  
  ////////////////////////////////////////////////////////////////////
  //////////////////////////   main   ////////////////////////////////
  ////////////////////////////////////////////////////////////////////
  int main(int argc, char const *argv[])
  {
  
      std::vector&lt;int&gt; vec(5);
      for (int i = 0; i &lt; vec.size(); ++i)
          vec[i] = i;
  
      TREE aTree;
      TNode* root =  aTree.createBBST(vec, 0, vec.size()-1);
  
      //print the resulted BBST
      aTree.inOrderTraverseBT( root );
  
      //search a key
      TNode* node = aTree.searchBBST(root, 3);
      if(node != NULL)
          cout &lt;&lt; "node-&gt;data = " &lt;&lt; node-&gt;data &lt;&lt; endl;
      else
          cout &lt;&lt; "Key not found..." &lt;&lt; endl;
  
      //insert
      cout &lt;&lt; "Insert node : 3" &lt;&lt; endl;
      aTree.insertBBST(root, 3);
      aTree.inOrderTraverseBT( root );
  
  
      cout &lt;&lt; "Insert node : 8"  &lt;&lt; endl;
      aTree.insertBBST(root, 8);
      aTree.inOrderTraverseBT( root );
      aTree.deleteBBST(root, 8);
      // aTree.inOrderTraverseBT( root );
  
      return 0;
  }
  </code></pre>