Write C++ Problem 1: Design an algorithm to remove items from a binary search tr

Question

Write C++

Problem 1: Design an algorithm to remove items from a binary search tree. This algorithm differs from the one described in the trees lecture when a node N has two children. First let N ’s right child take the place of the deleted node N in the same manner in which you delete a node with one child. Next reconnect N ’s left child (along with its sub-tree, if any) to the left side of the node containing the in-order successor of the value in N. Implement this design in C++.

Design:

Code:

Output:

Explanation / Answer

CODE:

#include<iostream>
using namespace std;

bool c=false;

struct node
{
   int data;
   node* left_c;
   node* right_c;
};

struct node* getNode(int data)
{
   node* newNode=new node();
   newNode->data=data;
   newNode->left_c=NULL;
   newNode->right_c=NULL;
   return newNode;
}

void inorder(struct node* root)
{
if (root != NULL)
{
inorder(root->left_c);
cout<<root->data<<" ";
inorder(root->right_c);
}
}

node* findMin(node*root)
{
while(root->left_C!=NULL)
{
root=root->left_C;
}
return root;
}

struct node* Insert(struct node* root, int data)
{
   if (root == NULL)
       return getNode(data);

   if (data < root->data)
       root->left_C = Insert(root->left_c, data);
   else if (data > root->data)
       root->right_c = Insert(root->right_c, data);

   return root;
}

bool Search(node*root,int value)
{
   if(root==NULL)
       return false;
   else if(root->data == value)
   {
       return true;
   }
   else if(value < root-> data)
       Search(root->left_c,value);
   else if(value > root->data)
       Search(root->right_c,value);
}

node* Delete( node* root,int value)
{
   c=Search(root,value);
   if(root==NULL)
       return root;
   else if(value< root->data)
   {
       root->left_C= Delete(root->left_c,value);
   }
   else if(value> root->data)
   {
       root->right_C= Delete(root->right_c,value);
   }
  
   // Node deletion
   else
   {
       //case 1: Leaf Node
       if(root->left_C==NULL&&root->right_c==NULL)
       {
           delete root;
           root=NULL;
           return root;
       }
       //case 2: one child
       else if(root->left_c==NULL)
       {
           struct node* temp=root;
           root=root->right_c;
           delete temp;
           return root;
       }
       else if(root->right_c==NULL)
       {
           struct node* temp=root;
           root=root->left_c;
           delete temp;
           return root;
       }
       //case 3: 2 child
       else
       {
           struct node*temp=findMin(root->right_c);
           root->data=temp->data;
           root->right_c=Delete(root->right_c,temp->data);
       }
   }
   return root;

}

int main()
{
   node* root=NULL;
   root=Insert(root,20);
   Insert(root,15);
   Insert(root,25);
   Insert(root,18);
   Insert(root,10);
   Insert(root,16);
   Insert(root,19);
   Insert(root,17);

   cout<<"Nodes Before Deletion: "<<endl;
   cout<<"Inorder: ";
   inorder(root);
   cout<<endl<<endl;

   Delete(root,15);

   if(c)
   {   
       cout<<"Nodes Deleted"<<endl;
       cout<<" Nodes After Deletion: "<<endl;
       cout<<"Inorder: ";
       inorder(root);
       cout<<endl;
   }
   else
       cout<<"Node Not Found"<<endl;

   return 0;

}

Output:

Nodes Before Deletion:
Inorder: 10 15 16 17 18 19 20 25
Nodes Deleted
Nodes After Deletion:
Inorder: 10 16 17 18 19 20 25

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.