Code for the deletion in BST case 3

#1

#include
#include
using namespace std;

class node{
public:
int data;
nodeleft;
noderight;

    node(int d){
        data = d;
        left = NULL;
        right = NULL;
    }

};

//Accepts the old root node & data and returns the new root node
node* insertInBST(node *root,int data){
//Base Case
if(root==NULL){
return new node(data);
}
//Rec Case - Insert in the Subtree and Update Pointers
if(data<=root->data){
root->left = insertInBST(root->left,data);
}
else{
root->right = insertInBST(root->right,data);
}
return root;
}

bool search(node*root,int data){
if(root==NULL){
return false;
}
if(root->data==data){
return true;
}
//Recursively search in left and right subtree
if(data<=root->data){
return search(root->left,data);
}
else{
return search(root->right,data);
}
}

node* build(){
//Read a list of numbers till -1 and also these numbers will be inserted into BST
int d;
cin>>d;

node*root = NULL;

while(d!=-1){
    root = insertInBST(root,d);
    cin>>d;
}
return root;

}
//Print the BST Level By Level
void bfs(node root){
queue<node> q;
q.push(root);
q.push(NULL);

while(!q.empty()){
    node* f = q.front();
    if(f==NULL){
        cout<<endl;
        q.pop();
        if(!q.empty()){
            q.push(NULL);
        }
    }
    else{
        cout<<f->data<<",";
        q.pop();

        if(f->left){
            q.push(f->left);
        }
        if(f->right){
            q.push(f->right);
        }
    }
}
return;

}
//Inorder Print
void inorder(node*root){
if(root==NULL){
return;
}
inorder(root->left);
cout<data<<",";
inorder(root->right);
}

node* deleteInBST(noderoot,int data){
if(root==NULL){
return NULL;
}
else if(datadata){
root->left = deleteInBST(root->left,data);
return root;
}
else if(data==root->data){
//Found the node to delete 3 Cases
//1. Node with 0 children - Leaf Node
if(root->left==NULL && root->right==NULL){
delete root;
return NULL;
}
//2. Case Only 1 child
if(root->left!=NULL && root->right==NULL){
node temp = root->left;
delete root;
return temp;
}
if(root->right!=NULL && root->left==NULL){
node* temp = root->right;
delete root;
return temp;
}
//3. Case 2 children
node *replace = root->right;
//Find the inorder successor from right subtree
while(replace->left!=NULL){
replace = replace->left;
}
root->data = replace->data;
root->right = deleteInBST(root->right,replace->data);
return root;
}
else{
root->right = deleteInBST(root->right,data);
return root;
}
}

int main(){
node*root = build();
inorder(root);
cout<<endl;

int s;
cin>>s;
root = deleteInBST(root,s);
inorder(root);
cout<<endl;
bfs(root);

return 0;
}

root->right = deleteInBST(root->right,data);
i think in this line…root->right means we have come to riight of head of tree…now we should call on the root->left inside the DeleInBST function inorder to reach lowest integer…so why are we writing root->right in DeleteInBST…?

#2

@ynikhil1999 hey nikhil share your code through cb.lk/ide.

#3
#4

@ynikhil1999 hey nikhil try to replace the left->root instead of right->root.

#5

u didnt get my question

#6

@ynikhil1999 hey Nikhil I got your point due to the third case your output was different because of this I suggested replacing the left root instead of right one
for reference, I am attaching your code
node replace =root->right;
//Find the inorder successor from right subtree
while(replace->left!=NULL){
replace = replace->left;
}
root->data = replace->data;
root->right = deleteInBST(root->right,replace->data);
return root;
}
see the highlighted text now think this movement how to replace the root left as node replace

1 Like
#7

is there any way so that we can generate inorder by seing preoder…?

#8

@ynikhil1999 hey nikhil I think you have created a separate doubt thread for this question and that thread was responded.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.