deletion in a binary search tree

1//insertion;deletion;searching;dispaly;menu driven program ;(BINARY SEARCH TREE)
2#include <iostream>
3
4using namespace std;
5class node
6{
7public:
8    int data;
9    node*right;
10    node*left;
11};
12node*getnewnode(int val)
13{
14    node *temp=new node;
15    temp->data=val;
16    temp->left=NULL;
17    temp->right=NULL;
18   return temp;
19}
20int getrightmin(node*root)
21{
22    node*temp=new node;
23    temp=root;
24    while(temp->left!=NULL)
25    {
26        temp=temp->left;
27    }
28    return temp->data;
29}
30node*insertbst(node*root,int val)
31{
32    if(root==NULL)
33    {
34        return getnewnode(val);
35    }
36    if(root->data>val)
37    {
38        root->left= insertbst(root->left,val);
39    }
40    else
41    {
42        root->right= insertbst(root->right,val);
43    }
44    return root;
45}
46int searchbst(node*root,int val)
47{
48    if(root==NULL)
49    {
50        return 0;
51    }
52    if(root->data==val)
53    {
54        return 1;
55    }
56    if(root->data<val)
57    {
58        return searchbst(root->right,val);
59    }
60    else
61    {
62        return searchbst(root->left,val);
63    }
64}
65node*removebst(node*root,int val)
66{
67    if(root==NULL)
68    {
69        return 0;
70    }
71    if(root->data>val)
72    {
73        root->left=removebst(root->left,val);
74    }
75    else if(root->data<val)
76    {
77        root->right=removebst(root->right,val);
78    }
79    else
80    {
81        if(root->left==NULL&&root->right==NULL)
82        {
83            delete root;
84            return NULL;
85        }
86        else if(root->left==NULL)
87        {
88            node*temp=new node;
89            temp=root->right;
90            delete root;
91            return temp;
92        }
93        else if(root->right==NULL)
94        {
95            node*temp=new node;
96            temp=root->left;
97            delete root;
98            return temp;
99        }
100        else
101        {
102            int min=getrightmin(root->right);
103            root->data=min;
104            root->right=removebst(root->right,min);
105        }
106    }
107    return root;
108}
109void inorder(node*root)
110{
111    if(root==NULL)
112    {
113        return;
114    }
115    inorder(root->left);
116    cout<<root->data<<" ";
117    inorder(root->right);
118}
119int main()
120{
121    node*root=new node;
122    root=NULL;
123    while(1)
124    {
125        int value;
126        cout<<"1.Insert to bst"<<endl<<"2.search in bst:"<<endl<<"3.display ordered bst"<<endl<<"4. exit"<<endl<<"5. delete "<<endl;
127        int n;
128        cout<<"enter your choice:"<<endl;
129        cin>>n;
130        switch(n)
131        {
132        case 1:
133            {
134                cout<<"enter the value to be inserted:"<<endl;
135                cin>>value;
136                root=insertbst(root,value);
137                break;
138            }
139        case 2:
140            {
141                cout<<"enter the value you want to search:"<<endl;
142                int search;
143                cin>>search;
144                int s=searchbst(root,search);
145                if(s==1)
146                {
147                    cout<<"value found"<<endl;
148                }
149                else
150                {
151                    cout<<"value not found:"<<endl;
152                }
153                break;
154            }
155        case 3:
156            {
157                inorder(root);
158                cout<<endl;
159                break;
160            }
161        case 4:
162            {
163                exit(0);
164                break;
165            }
166        case 5:
167            {
168                int val;
169                cout<<"enter the value to be deleted:"<<endl;
170                cin>>val;
171                removebst(root,val);
172                break;
173
174            }
175        default:
176            {
177                cout<<"invalid choice given:"<<endl;
178                break;
179            }
180
181        }
182    }
183    return 0;
184}
185

1/* This is just the deletion function you need to write the required code.
2	Thank you. */
3
4void deleteNode(Node *root, int data)
5{
6    if(root == NULL)
7    {
8        cout << "Tree is empty\n";
9        return;
10    }
11
12    queue<Node*> q;
13    q.push(root);
14
15    while(!q.empty())
16    {
17        Node *temp = q.front();
18        q.pop();
19
20        if(temp->data == data)
21        {
22            Node *current = root;
23            Node *prev;
24
25            while(current->right != NULL)
26            {
27                prev = current;
28                current = current->right;
29            }
30
31            temp->data = current->data;
32            prev->right = NULL;
33            free(current);
34
35            cout << "Deleted\n";
36
37            return;
38        }
39
40        if(temp->left != NULL)
41            q.push(temp->left);
42        if(temp->right != NULL)
43            q.push(temp->right);
44    }
45
46    cout << "Node not found for deletion\n";
47}