Skip to content
This repository was archived by the owner on Sep 7, 2025. It is now read-only.

Commit 0210cfb

Browse files
abranheabranhe
authored
Merge pull request #98 from bag-PacKer/master
Create BinarySearchTree.cpp
2 parents 7413038 + ccaf3bf commit 0210cfb

1 file changed

Lines changed: 170 additions & 0 deletions

File tree

‎data-structures/BinarySearchTree.cpp‎

Lines changed: 170 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,170 @@
1+
#include<bits/stdc++.h>
2+
#define ll long long int
3+
#define ull unsigned long long int
4+
#define pb push_back
5+
#define MIN 2
6+
#define sc(n) scanf("%d",&n)
7+
#define pr(n) printf("%d",n)
8+
#define gc getchar_unlocked
9+
#define AC 0
10+
#define MOD 1000000007
11+
#define mp make_pair
12+
#define vc vector
13+
#define wh(n) while(n--)
14+
#define ite(type,datatype,name) type<datatype>::iterator name
15+
#define gt goto
16+
17+
using namespace std;
18+
19+
/*Structure of node*/
20+
struct node{
21+
int data;
22+
struct node *left,*right;
23+
};
24+
/*Create a new Node*/
25+
struct node *newnode(int p){
26+
struct node *temp = new node();
27+
temp->data = p;
28+
temp->left = temp->right = NULL;
29+
return temp;
30+
}
31+
32+
/*Insert a new Node in BST*/
33+
struct node *insert(struct node *root,int p){
34+
if(root == NULL){
35+
return newnode(p);
36+
}
37+
if(root->data > p){
38+
root->left = insert(root->left,p);
39+
}
40+
else{
41+
root->right = insert(root->right,p);
42+
}
43+
return root;
44+
}
45+
/* Display BST */
46+
void display(struct node *root){
47+
if(root != NULL){
48+
cout<<root->data<<" "; //Pre-Order
49+
display(root->left);
50+
// cout<<root->data<<" ";
51+
display(root->right);
52+
53+
}
54+
}
55+
/*Return node with minimum value*/
56+
struct node *minvalue(struct node *root){
57+
struct node *curr = root;
58+
59+
while(curr->left != NULL){
60+
curr = curr->left;
61+
}
62+
return curr;
63+
}
64+
65+
/* Delete node with given key value in BST */
66+
struct node *del(struct node* root,int key){
67+
//Base case for root
68+
if(root == NULL) return root;
69+
if(root->data > key){
70+
root->left = del(root->left,key);
71+
}
72+
else if(root->data < key){
73+
root->right = del(root->right,key);
74+
}
75+
else{
76+
//noDe has one or nO noDe
77+
if(root->left == NULL){
78+
struct node *temp = root->right;
79+
free(root);
80+
return temp;
81+
}
82+
else if(root->right == NULL){
83+
struct node *temp = root->left;
84+
free(root);
85+
return temp;
86+
}
87+
//tWo chiLd
88+
struct node *temp = minvalue(root->right);
89+
root->data = temp->data;
90+
root->right = del(root->right,temp->data);
91+
}
92+
return root;
93+
}
94+
95+
/* Return height of BST */
96+
int maxheight(struct node *node){
97+
if(node == NULL){
98+
return 0;
99+
}
100+
int lh = maxheight(node->left);
101+
int rh = maxheight(node->right);
102+
103+
if(lh>rh) return (lh+1);
104+
else return (rh+1);
105+
}
106+
/* return the search value for given key */
107+
int search(struct node* temp,int key){
108+
int p=key;
109+
while(1){
110+
if(temp->data == key){
111+
return p;
112+
}
113+
else if(temp->data > key){
114+
p = max(p,temp->data);
115+
temp = temp->left;
116+
}
117+
else if(temp->data < key){
118+
temp = temp->right;
119+
}
120+
}
121+
return p;
122+
}
123+
124+
/*Print BST in zigzag Pattern */
125+
void zigzeg(struct node* root){
126+
stack<int> s[2];
127+
int curr = 0;
128+
int oth = 1;
129+
s[curr].push(root->data);
130+
struct node* temp1 = root;
131+
struct node* temp2 = root;
132+
while((!s[curr].empty()) || (!s[oth].empty())){
133+
if(curr == 0){
134+
int p = s[curr].top();
135+
s[curr].pop();
136+
s[oth].push(temp1->left->data);
137+
s[oth].push(temp1->right->data);
138+
temp1= temp1->right;
139+
cout<<p<<" ";
140+
}
141+
else{
142+
int p = s[oth].top();
143+
s[oth].pop();
144+
s[curr].push(temp1->right->data);
145+
s[curr].push(temp1->left->data);
146+
temp1= temp1->left;
147+
cout<<p<<" ";
148+
}
149+
if(s[curr].empty()){
150+
swap(curr,oth);
151+
}
152+
}
153+
}
154+
// Driver program to test above functions
155+
int main(){
156+
struct node *root = NULL;
157+
root = insert(root,20);
158+
insert(root,10);
159+
insert(root,30);
160+
insert(root,5);
161+
insert(root,15);
162+
insert(root,25);
163+
insert(root,35);
164+
insert(root,45);
165+
display(root);
166+
cout<<endl;
167+
cout<<"Height of tree is: "<<maxheight(root)<<endl;
168+
zigzeg(root);
169+
return 0;
170+
}

0 commit comments

Comments
 (0)