forked from AllAlgorithms/cpp
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinarySearchTree.cpp
More file actions
170 lines (161 loc) · 3.91 KB
/
BinarySearchTree.cpp
File metadata and controls
170 lines (161 loc) · 3.91 KB
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define MIN 2
#define sc(n) scanf("%d",&n)
#define pr(n) printf("%d",n)
#define gc getchar_unlocked
#define AC 0
#define MOD 1000000007
#define mp make_pair
#define vc vector
#define wh(n) while(n--)
#define ite(type,datatype,name) type<datatype>::iterator name
#define gt goto
using namespace std;
/*Structure of node*/
struct node{
int data;
struct node *left,*right;
};
/*Create a new Node*/
struct node *newnode(int p){
struct node *temp = new node();
temp->data = p;
temp->left = temp->right = NULL;
return temp;
}
/*Insert a new Node in BST*/
struct node *insert(struct node *root,int p){
if(root == NULL){
return newnode(p);
}
if(root->data > p){
root->left = insert(root->left,p);
}
else{
root->right = insert(root->right,p);
}
return root;
}
/* Display BST */
void display(struct node *root){
if(root != NULL){
cout<<root->data<<" "; //Pre-Order
display(root->left);
// cout<<root->data<<" ";
display(root->right);
}
}
/*Return node with minimum value*/
struct node *minvalue(struct node *root){
struct node *curr = root;
while(curr->left != NULL){
curr = curr->left;
}
return curr;
}
/* Delete node with given key value in BST */
struct node *del(struct node* root,int key){
//Base case for root
if(root == NULL) return root;
if(root->data > key){
root->left = del(root->left,key);
}
else if(root->data < key){
root->right = del(root->right,key);
}
else{
//noDe has one or nO noDe
if(root->left == NULL){
struct node *temp = root->right;
free(root);
return temp;
}
else if(root->right == NULL){
struct node *temp = root->left;
free(root);
return temp;
}
//tWo chiLd
struct node *temp = minvalue(root->right);
root->data = temp->data;
root->right = del(root->right,temp->data);
}
return root;
}
/* Return height of BST */
int maxheight(struct node *node){
if(node == NULL){
return 0;
}
int lh = maxheight(node->left);
int rh = maxheight(node->right);
if(lh>rh) return (lh+1);
else return (rh+1);
}
/* return the search value for given key */
int search(struct node* temp,int key){
int p=key;
while(1){
if(temp->data == key){
return p;
}
else if(temp->data > key){
p = max(p,temp->data);
temp = temp->left;
}
else if(temp->data < key){
temp = temp->right;
}
}
return p;
}
/*Print BST in zigzag Pattern */
void zigzeg(struct node* root){
stack<int> s[2];
int curr = 0;
int oth = 1;
s[curr].push(root->data);
struct node* temp1 = root;
struct node* temp2 = root;
while((!s[curr].empty()) || (!s[oth].empty())){
if(curr == 0){
int p = s[curr].top();
s[curr].pop();
s[oth].push(temp1->left->data);
s[oth].push(temp1->right->data);
temp1= temp1->right;
cout<<p<<" ";
}
else{
int p = s[oth].top();
s[oth].pop();
s[curr].push(temp1->right->data);
s[curr].push(temp1->left->data);
temp1= temp1->left;
cout<<p<<" ";
}
if(s[curr].empty()){
swap(curr,oth);
}
}
}
// Driver program to test above functions
int main(){
struct node *root = NULL;
root = insert(root,20);
insert(root,10);
insert(root,30);
insert(root,5);
insert(root,15);
insert(root,25);
insert(root,35);
insert(root,45);
display(root);
cout<<endl;
cout<<"Height of tree is: "<<maxheight(root)<<endl;
zigzeg(root);
return 0;
}