forked from ReciHub/FunnyAlgorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
BST.cpp
131 lines (114 loc) · 1.92 KB
/
BST.cpp
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
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node*left;
node*right;
node(int d)
{
data=d;
left=NULL;
right=NULL;
}
};
node* insert(node*root,int data)
{
if(root==NULL){
return root=new node(data);}
if(data<root->data)
{
root->left=insert(root->left,data);
}
else
root->right=insert(root->right,data);
return root;
}
bool search(node*root,int data)
{
if(root==NULL)
return false;
else if(data<root->data)
return search(root->left,data);
else
return search(root->right,data);
return true;
}
node* delete_node(node*root,int data)
{
if(root==NULL)
return NULL;
else if(data<root->data)
return delete_node(root->left,data);
//3 cases
else if(data==root->data)
{
//for leaf node
if(root->left==NULL and root->right==NULL)
{
delete root;
return NULL;
}
//for node having 1 child
if(root->left!=NULL and root->right==NULL)
{
//store root's left child in a temporary node
node*temp=root->left;
delete root;
return temp;
}
if(root->left==NULL and root->right!=NULL)
{
node*temp=root->right;
delete root;
return temp;
}
//for 2 child node
node* replace=root->right;
while(root->left!=NULL)
replace=replace->left;
replace->data=root->data;
root->right=delete_node(root->right,replace->data);
return root;
}
else
return delete_node(root->right,data);
}
bool is_BST(node*root,int min=INT_MIN,int max=INT_MAX)
{
if(root==NULL)
return false;
if(root->data<min and root->data>max and is_BST(root->left,min,root->data) and is_BST(root->right,root->data,max))
{
return true;
}
return false;
}
node* build()
{
int d;
cin>>d;
node*root=NULL;
while(d!=-1)
{
root=insert(root,d);
cin>>d;
}
return root;
}
void print(node*root)
{
if(root==NULL)
return;
cout<<root->data<<" ->";
print(root->left);
print(root->right);
}
int main()
{
node *root=build();
// build();
print(root);
return 0;
}