Question

8.16 Implement code for the BSTRemove operation.

Implement node removal functionality for the BinarySearchTree. The base remove function has already been implemented for you, but you need to fill in the implementation for Case 1, Case 2, and Case 3 of the algorithm as described in the lecture notes.

Note, the pseudo-code in the lecture should work with minimal modifications. However, it would be a good learning exercise to try to implement them from scratch if you have time.

//C++ code

#include <iostream>
#include <random>

class BinarySearchTree {
protected:
// Class to represent a node of a binary tree
class BTNode
{
public:
int data;
BTNode *right;
BTNode *left;
  
BTNode(int d, BTNode *l=nullptr, BTNode *r=nullptr)
{
data = d;
right = r;
left = l;

}
};

BTNode *root;
  
public:
BinarySearchTree()
{
root = nullptr;
}

~BinarySearchTree()
{
// UNCOMMENT ONCE REMOVE WORKS!
//while(root)
// remove(root->data);
}

void insert(int data)
{
BTNode *node = new BTNode(data);

if (root == nullptr)
{
   root = node;
}
else
{   
   BTNode * tmp = root;
   while (tmp != nullptr)
   {  
   if (data < tmp->data)
   {
       // data must be on left side
       if (tmp->left == nullptr)
       {
       tmp->left = node; //
       return;
       }
       else
       tmp = tmp->left;
   }
   else
   {
       // data must be on right side
       if (tmp->right == nullptr)
       {
       tmp->right = node;
       return;      
       }
       else
       tmp = tmp->right;
   }
   }
}

}

bool search(int data) {
BTNode * tmp = root;
while (tmp != nullptr)
{
   if (data == tmp->data)
   return true;
  
   if (data < tmp->data)
   tmp = tmp->left;
   else
   tmp = tmp->right;
}
return false;
}

private:
bool Case1(BTNode *node, BTNode *parent)
{
return false; // not Case 1, try Case 2
}

bool Case2(BTNode *node, BTNode *parent)
{
return false; // not Case 1 or 2, must use Case 3
}

bool Case3(BTNode *node, BTNode *parent)
{
// Case 3 must succeed!
return true;
}
  
public:
void remove(int data) {
BTNode *tmp = root;
BTNode *parent = nullptr;
  
// Find the node in the tree
while (tmp != nullptr)
{
   if (tmp->data == data)
   {
   if (!Case1(tmp,parent))
   if (!Case2(tmp,parent))
       Case3(tmp,parent);

   // delete node once removed  
   //delete tmp; // UNCOMMENT ONCE REMOVE WORKS
   break;
   }          
   else if (data < tmp->data)
   {
   parent = tmp;
   tmp = tmp->left;
   }
   else
   {
   parent = tmp;
   tmp = tmp->right;
   }
}
}

public:
// DO NOT REMOVE OR MODIFY

bool hasRoot() {
return root != nullptr;
}

int getRoot() {
if (hasRoot()) return root->data;
else return -1;
}

bool rootHasRightChild() {
return root->right != nullptr;
}

int getRootRightChild() {
return root->right->data;
}

bool rootHasLeftChild() {
return root->left != nullptr;
}

int getRootLeftChild() {
return root->left->data;
}
public:
friend std::ostream& operator<< (std::ostream& out, BTNode *bt);
friend std::ostream& operator<< (std::ostream& out, BinarySearchTree &bst);
};

std::ostream& operator<< (std::ostream& out, BinarySearchTree::BTNode *bt)
{
if (bt == nullptr)
return out;
  
if (bt->left != nullptr)
out << bt->left;

out << bt->data << " ";

if (bt->right != nullptr)
out << bt->right;

return out;
}

std::ostream& operator<< (std::ostream& out, BinarySearchTree &bst)
{
out << bst.root;
return out;
}

int main()
{
//std::random_device generator;
std::default_random_engine generator;
std::uniform_int_distribution<int> dist(0,1000);

BinarySearchTree *b2 = new BinarySearchTree();
for(int i=0; i<10; i++)
{
b2->insert(dist(generator));
}
for (int i=0; i<5; i++)
b2->insert(i*100);
for(int i=0; i<10; i++)
{
b2->insert(dist(generator));
}

std::cout << *b2 << std::endl;

for (int i=0; i<5; i++)
{
std::cout << "remove " << i*100 << std::endl;
b2->remove(i*100);
}
std::cout << *b2;

delete b2;
  
return 0;
}

Answer 1

Case1, Case2 and Case3 are implemented below:

bool Case1(BTNode *node, BTNode *parent)
{
    //if the node to be deleted is the leaf node
    if(node->left == NULL && node->right == NULL){

        //make the left or right child of parent node null
        //depending on whether the node is greater or smaller than the parent
        if(node->data < parent->data)
            parent->left = NULL;
        else parent->right = NULL;

        return true;
    }
       
    return false; // not Case 1, try Case 2
}



bool Case2(BTNode *node, BTNode *parent)
{ if(node->data == 200) cout<<"ahhs"<<endl;
    //if the ndoe to be deleted has only one child
    if((node->right == NULL && node->left != NULL) || (node->left == NULL && node->right != NULL)){
        
         if(parent == NULL) root = node->left;
        //if there is only the left child
        //then append the child node to parent of node to be deleted
        if(node->left){
            if(node->data == 200) cout<<"left"<<endl;
            //if node is in the left of the parent
            //add left child to left of the parent
            if(node->data <  parent->data){
                parent->left = node->left;
            }
            //add left child to right of the parent
            else{
                parent->right = node->left;
            }
            
        }


        //if there is only the right child
        //then append the child node to parent of node to be deleted
        else if(node->right){
            if(node->data == 200) cout<<"right"<<endl;
            if(parent == NULL) root = node->right;
            
            //if node is in the left of the parent
            //add right child to left of the parent
            else if(node->data < parent->data){
               
                parent->left = node->right;
            }
            //add right child to right of the parent
            else{
                parent->right = node->right;
            }
        }
    }
    return false; // not Case 1 or 2, must use Case 3
}



bool Case3(BTNode *node, BTNode *parent)
{
    //if the node has both the childs
    //no need to do this check
    //but its always healthy to do so
    if(node->left && node->right){

        //replace the node by its inorder predecessor
        BTNode *temp = node->right, *parent_temp = node;
        while(temp->left && temp->right){
            parent_temp = temp;
            temp = temp->left;
        }


        //temp is our inorder predecessor

        //if the node->right is the inorder predecessor of node
        if(parent_temp != node){
            parent_temp->left = NULL;
            temp->left = node->left;
            temp->right = NULL;
        }

        //if the node is in the left of parent
        else if(parent->data > node->data){
            parent->left = temp;
             temp->left = node->left;
            temp->right = node->right;
        }
        //if the node is in the right of parent
        else{
            parent->right = temp;
            temp->left = node->left;
            temp->right = node->right;
        }

       

    }
    return true;
}

Output:

if it helps you, do upvote as it motivates us a lot!