forked from bhargav-joshi/LearnFree
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDelete a node from the BST
126 lines (119 loc) · 2.39 KB
/
Delete a node from the BST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
using namespace std;
struct node
{
int data;
node* left;
node* right;
};
node* root=NULL;
node* getnew(int data)
{
node*temp=new node();
temp->data=data;
temp->left=temp->right=NULL;
return temp;
}
node* insert(node* root,int data)
{
if(root==NULL)
{
root=getnew(data);
}
else if(data<=root->data)
{
root->left=insert(root->left,data);
}
else
{
root->right=insert(root->right,data);
}
return root;
}
void print(node* root)
{
if(root==NULL)return;
print(root->left);
cout<<root->data<<" ";
print(root->right);
}
node* findmin(node*root)
{
if(root==NULL)
{
return 0;
}
node* temp=root;
while(temp!=NULL)
{
temp=temp->left;
}
return root;
}
node* Delete(node* root,int data)
{
if(root==NULL)
{
return root;
}
else if(data<root->data)
{
root->left=Delete(root->left,data);
}
else if(data>root->data)
{
root->right=Delete(root->right,data);
}
else
{
//case1 where node is leaf
if(root->left==NULL&& root->right==NULL)
{
delete root;
root=NULL;
}
//case2 where node has 1 child
else if(root->left==NULL)
{
node* temp=root;
root=temp->right;
delete temp;
}
else if(root->right==NULL)
{
node* temp=root;
root=temp->left;
delete temp;
}
//case 3 where node has 2 child then we find mininmum of right sub-tree or the max of left sub-tree then swap
else
{
node* temp=findmin(root->right);
root->data=temp->data;
root->right=Delete(root->right,temp->data);
}
}
return root;
}
int main()
{
node* root=NULL;
cout<<"enter the no. of nodes you want to inser in the list\n:";
int range,data;
cin>>range;
for(int i=1;i<=range;i++)
{
cout<<"enter the "<<i<<" number\n:";
cin>>data;
root=insert(root,data);
}
cout<<"the tree is\n";
print(root);
cout<<"\nenter the number you want to delete from the tree\n:";
int del;
cin>>del;
cout<<"after the deletion the list is\n:";
root=Delete(root,del);
print(root);
return 0;
}