Answers for "deletion in a binary search tree"

deletion in a binary search tree

//insertion;deletion;searching;dispaly;menu driven program ;(BINARY SEARCH TREE)
#include <iostream>

using namespace std;
class node
{
public:
    int data;
    node*right;
    node*left;
};
node*getnewnode(int val)
{
    node *temp=new node;
    temp->data=val;
    temp->left=NULL;
    temp->right=NULL;
   return temp;
}
int getrightmin(node*root)
{
    node*temp=new node;
    temp=root;
    while(temp->left!=NULL)
    {
        temp=temp->left;
    }
    return temp->data;
}
node*insertbst(node*root,int val)
{
    if(root==NULL)
    {
        return getnewnode(val);
    }
    if(root->data>val)
    {
        root->left= insertbst(root->left,val);
    }
    else
    {
        root->right= insertbst(root->right,val);
    }
    return root;
}
int searchbst(node*root,int val)
{
    if(root==NULL)
    {
        return 0;
    }
    if(root->data==val)
    {
        return 1;
    }
    if(root->data<val)
    {
        return searchbst(root->right,val);
    }
    else
    {
        return searchbst(root->left,val);
    }
}
node*removebst(node*root,int val)
{
    if(root==NULL)
    {
        return 0;
    }
    if(root->data>val)
    {
        root->left=removebst(root->left,val);
    }
    else if(root->data<val)
    {
        root->right=removebst(root->right,val);
    }
    else
    {
        if(root->left==NULL&&root->right==NULL)
        {
            delete root;
            return NULL;
        }
        else if(root->left==NULL)
        {
            node*temp=new node;
            temp=root->right;
            delete root;
            return temp;
        }
        else if(root->right==NULL)
        {
            node*temp=new node;
            temp=root->left;
            delete root;
            return temp;
        }
        else
        {
            int min=getrightmin(root->right);
            root->data=min;
            root->right=removebst(root->right,min);
        }
    }
    return root;
}
void inorder(node*root)
{
    if(root==NULL)
    {
        return;
    }
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}
int main()
{
    node*root=new node;
    root=NULL;
    while(1)
    {
        int value;
        cout<<"1.Insert to bst"<<endl<<"2.search in bst:"<<endl<<"3.display ordered bst"<<endl<<"4. exit"<<endl<<"5. delete "<<endl;
        int n;
        cout<<"enter your choice:"<<endl;
        cin>>n;
        switch(n)
        {
        case 1:
            {
                cout<<"enter the value to be inserted:"<<endl;
                cin>>value;
                root=insertbst(root,value);
                break;
            }
        case 2:
            {
                cout<<"enter the value you want to search:"<<endl;
                int search;
                cin>>search;
                int s=searchbst(root,search);
                if(s==1)
                {
                    cout<<"value found"<<endl;
                }
                else
                {
                    cout<<"value not found:"<<endl;
                }
                break;
            }
        case 3:
            {
                inorder(root);
                cout<<endl;
                break;
            }
        case 4:
            {
                exit(0);
                break;
            }
        case 5:
            {
                int val;
                cout<<"enter the value to be deleted:"<<endl;
                cin>>val;
                removebst(root,val);
                break;

            }
        default:
            {
                cout<<"invalid choice given:"<<endl;
                break;
            }

        }
    }
    return 0;
}

binary tree deletion

/* This is just the deletion function you need to write the required code.
	Thank you. */

void deleteNode(Node *root, int data)
{
    if(root == NULL)
    {
        cout << "Tree is empty\n";
        return;
    }

    queue<Node*> q;
    q.push(root);

    while(!q.empty())
    {
        Node *temp = q.front();
        q.pop();

        if(temp->data == data)
        {
            Node *current = root;
            Node *prev;

            while(current->right != NULL)
            {
                prev = current;
                current = current->right;
            }

            temp->data = current->data;
            prev->right = NULL;
            free(current);

            cout << "Deleted\n";

            return;
        }

        if(temp->left != NULL)
            q.push(temp->left);
        if(temp->right != NULL)
            q.push(temp->right);
    }

    cout << "Node not found for deletion\n";
}