AVL Tree with Insertion,Deletion and balancing Height

# include < conio.h > 
# include < process.h > 
# include < iostream.h > 
# include < alloc.h > 
struct node 
{ 
int ele; 
node *left; 
node *right; 
}; 
typedef struct node *nodeptr; 
class stack 
{ 
private: 
struct snode 
{ 
nodeptr ele; 
snode *next; 
}; 
snode *top; 
public: 
stack() 
{ 
top=NULL; 
} 
void push(nodeptr p) 
{ 
snode *temp; 
temp = new snode; 
temp->ele = p; 
temp->next = top; 
top=temp; 
} 
void pop() 
{ 
if (top != NULL) 
{ 
nodeptr t; 
snode *temp; 
temp = top; 
top=temp->next; 
delete temp; 
} 
} 
nodeptr topele() 
{ 
if (top !=NULL) 
return top->ele; 
else 
return NULL; 
} 
int isempty() 
{ 
return ((top == NULL) ? 1 : 0); 
} 
}; 
class bstree 
{ 
public: 
void insert(int,nodeptr &); 
void del(int,nodeptr &); 
int deletemin(nodeptr &); 
void find(int,nodeptr &); 
nodeptr findmin(nodeptr); 
nodeptr findmax(nodeptr); 
void copy(nodeptr &,nodeptr &); 
void makeempty(nodeptr &); 
nodeptr nodecopy(nodeptr &); 
void preorder(nodeptr); 
void inorder(nodeptr); 
void postorder(nodeptr); 
void preordernr(nodeptr); 
void inordernr(nodeptr); 
void postordernr(nodeptr); 
void leftchild(int,nodeptr &); 
void rightchild(int,nodeptr &); 
}; 
void bstree::insert(int x,nodeptr &p) 
{ 
if (p==NULL) 
{ 
p = new node; 
p->ele=x; 
p->left=NULL; 
p->right=NULL; 
} 
else 
{ 
if (x < p->ele) 
insert(x,p->left); 
else if (x>p->ele) 
insert(x,p->right); 
else 
cout<<"Element already Exits !"; 
} 
} 
void bstree:: del(int x,nodeptr &p) 
{ 
nodeptr d; 
if (p==NULL) 
cout<<"Element not found "; 
else if (x < p->ele) 
del(x,p->left); 
else if (x > p->ele) 
del(x,p->right); 
else if ((p->left == NULL) && (p->right ==NULL)) 
{ 
d=p; 
free(d); 
p=NULL; 
} 
else if (p->left == NULL) 
{ 
d=p; 
free(d); 
p=p->right; 
} 
else if (p->right ==NULL) 
{ 
d=p; 
p=p->left; 
free(d); 
}
else 
p->ele=deletemin(p->right); 
} 
int bstree::deletemin(nodeptr &p) 
{ 
int c; 
if (p->left == NULL) 
{ 
c=p->ele; 
p=p->right; 
return c; 
} 
else 
c=deletemin(p->left); 
return c; 
} 
void bstree::copy(nodeptr &p,nodeptr &p1) 
{ 
makeempty(p1); 
p1=nodecopy(p); 
} 
void bstree::makeempty(nodeptr &p) 
{ 
nodeptr d; 
if (p!=NULL) 
{ 
makeempty(p->left); 
makeempty(p->right); 
d=p; 
free(d); 
p=NULL; 
} 
} 
nodeptr bstree::nodecopy(nodeptr &p) 
{ 
nodeptr temp; 
if (p == NULL) 
return p; 
else 
{ 
temp = new node; 
temp->ele=p->ele; 
temp->left = nodecopy(p->left); 
temp->right = nodecopy(p->right); 
return temp; 
} 
} 
nodeptr bstree::findmin(nodeptr p) 
{ 
if (p==NULL) 
{ 
cout<<"Tree is empty !"; 
return p; 
} 
else 
{ 
while (p->left !=NULL) 
p=p->left; 
return p; 
} 
} 
nodeptr bstree::findmax(nodeptr p) 
{ 
if (p==NULL) 
{ 
cout<<"Tree is empty !"; 
return p; 
} 
else 
{ 
while (p->right !=NULL) 
p=p->right; 
return p; 
} 
} 
void bstree::find(int x,nodeptr &p) 
{
if (p==NULL) 
cout<<"Element not found !"; 
else 
{ 
if (x < p->ele) 
find(x,p->left); 
else if ( x> p->ele) 
find(x,p->right); 
else 
cout<<"Element Found !"; 
} 
} 
void bstree::preorder(nodeptr p) 
{ 
if (p!=NULL) 
{ 
cout<< p->ele<<"-->"; 
preorder(p->left); 
preorder(p->right); 
} 
} 
void bstree::inorder(nodeptr p) 
{ 
if (p!=NULL) 
{ 
inorder(p->left); 
cout<< p->ele<<"-->"; 
inorder(p->right);
} 
} 
void bstree::postorder(nodeptr p) 
{ 
if (p!=NULL) 
{ 
postorder(p->left); 
postorder(p->right); 
cout<< p->ele<<"-->"; 
}

} 
void bstree::preordernr(nodeptr p) 
{ 
stack s; 
while (1) 
{ 
if (p != NULL) 
{ 
cout<< p->ele<<"-->"; 
s.push(p); 
p=p->left; 
} 
else if (s.isempty()) 
{ 
cout<<"Stack is empty"; 
return; 
} 
else 
{ 
nodeptr t; 
t=s.topele(); 
p=t->right; 
s.pop(); 
} 
} 
} 
void bstree::inordernr(nodeptr p) 
{ 
stack s; 
while (1) 
{ 
if (p != NULL) 
{ 
s.push(p); 
p=p->left; 
} 
else 
{ 
if (s.isempty()) 
{ 
cout<<"Stack is empty"; 
return; 
} 
else 
{ 
p=s.topele();
cout<< p->ele<<"-->"; 
} 
s.pop(); 
p=p->right; 
} 
} 
} 
void bstree::postordernr(nodeptr p) 
{ 
stack s; 
while (1) 
{ 
if (p != NULL) 
{ 
s.push(p); 
p=p->left; 
} 
else 
{ 
if (s.isempty()) 
{ 
cout<<"Stack is empty"; 
return; 
} 
else 
if (s.topele()->right == NULL) 
{ 
p=s.topele(); 
s.pop(); 
cout<< p->ele<<"-->"; 
if (p==s.topele()->right) 
{ 
cout<< s.topele()->ele<<"-->"; 
s.pop(); 
} 
} 
if (!s.isempty()) 
p=s.topele()->right; 
else 
p=NULL; 
} 
} 
} 
void bstree::leftchild(int q,nodeptr &p) 
{ 
if (p==NULL) 
cout<<"The node does not exists "; 
else 
if (q < p->ele ) 
leftchild(q,p->left); 
else 
if (q > p->ele) 
leftchild(q,p->right); 
else 
if (q == p->ele) 
{ 
if (p->left != NULL) 
cout<<"Left child of "<< q<<"is "<< p->left->ele; 
else 
cout<<"No Left child !"; 
} 
} 
void bstree::rightchild(int q,nodeptr &p) 
{ 
if (p==NULL) 
cout<<"The node does not exists "; 
else 
if (q < p->ele ) 
rightchild(q,p->left); 
else 
if (q > p->ele) 
rightchild(q,p->right); 
else 
if (q == p->ele) 
{ 
if (p->right != NULL) 
cout<<"Right child of "<< q<<"is "<< p->right->ele; 
else 
cout<<"No Right Child !"; 
} 
} 
int main() 
{ 
int ch,x,leftele,rightele; 
bstree bst; 
char c='y'; 
nodeptr root,root1,min,max; 
root=NULL; 
root1=NULL; 
do 
{ 
// system("clear");
clrscr(); 
cout<<"Binary Search Tree "; 
cout<<"-------------------------"; 
cout<<"1.Insertion 
2.Deletion 
3.NodeCopy"; 
cout<<"4.Find 
5.Findmax 
6.Findmin"; 
cout<<"7.Preorder 
8.Inorder 
9.Postorder"; 
cout<<"10.Leftchild 
11.Rightchild 
0.Exit"; 
cout<<"Enter your choice :"; 
cin>>ch; 
switch(ch) 
{ 
case 1: 
cout<<"1.Insertion"; 
cout<<"Enter the new element to get inserted :"; 
cin>>x; 
bst.insert(x,root); 
cout<<"Inorder traversal is :"; 
bst.inorder(root); 
break; 
case 2: 
cout<<"2.Deletion"; 
cout<<"Enter the element to get deleted :"; 
cin>>x; 
bst.del(x,root); 
bst.inorder(root); 
break; 
case 3: 
cout<<"3.Nodecopy"; 
bst.copy(root,root1); 
cout<<"The new tree is :"; 
bst.inorder(root1); 
break; 
case 4: 
cout<<"4.Find"; 
cout<<"Enter the element to be searched :"; 
cin>>x; 
bst.find(x,root); 
break; 
case 5: 
cout<<"5.Findmax"; 
if (root == NULL) 
cout<<"Tree is empty"; 
else 
{ 
max=bst.findmax(root); 
cout<<"Largest element is : "<< max->ele<< endl; 
} 
break; 
case 6: 
cout<<"6.Findmin"; 
if (root == NULL) 
cout<<"Tree is empty"; 
else 
{ 
min=bst.findmin(root); 
cout<<"Smallest element is : "<< min->ele<< endl; 
} 
break; 
case 7: 
cout<<"7.Preorder"; 
if (root==NULL) 
cout<<"Tree is empty"; 
else 
{ 
cout<<"Preorder traversal (Non-Recursive) is :"; 
bst.preordernr(root); 
cout<<"Preorder traversal (Recursive) is :"; 
bst.preorder(root); 
} 
break; 
case 8: 
cout<<"8.Inorder"; 
if (root==NULL) 
cout<<"Tree is empty"; 
else 
{ 
cout<<"Inorder traversal (Non-Recursive) is :"; 
bst.inordernr(root); 
cout<<"Inorder traversal (Recursive) is :"; 
bst.inorder(root); 
} 
break; 
case 9: 
cout<<"9.Postorder"; 
if (root==NULL) 
cout<<"Tree is empty"; 
else 
{ 
cout<<"Postorder traversal (Non-Recursive) is :"; 
bst.postordernr(root); 
cout<<"Postorder traversal (Recursive) is :"; 
bst.postorder(root); 
} 
break; 
case 10: 
cout<<"10.Finding the left Child "; 
if (root==NULL) 
cout<<"Tree is empty"; 
else 
{ 
cout<<"Enter the node for which the left child is to be found :"; 
cin>>leftele; 
bst.leftchild(leftele,root); 
} 
break; 
case 11: 
cout<<"11.Finding the Right Child "; 
if (root==NULL) 
cout<<"Tree is empty"; 
else 
{ 
cout<<"Enter the node for which the Right child is to be found :"; 
cin>>rightele; 
bst.rightchild(rightele,root); 
} 
break; 
case 0: 
exit(0); #include < stdlib.h > 
#include < conio.h > struct node 
{ 
int element; 
node *left; 
node *right; 
int height; 
}; 
typedef struct node *nodeptr; 
class bstree 
{ 
public: 
void insert(int,nodeptr &); 
void del(int, nodeptr &); 
int deletemin(nodeptr &); 
void find(int,nodeptr &); 
nodeptr findmin(nodeptr); 
nodeptr findmax(nodeptr); 
void copy(nodeptr &,nodeptr &); 
void makeempty(nodeptr &); 
nodeptr nodecopy(nodeptr &); 
void preorder(nodeptr); 
void inorder(nodeptr); 
void postorder(nodeptr); 
 int bsheight(nodeptr); 
nodeptr srl(nodeptr &); 
nodeptr drl(nodeptr &); 
nodeptr srr(nodeptr &); 
nodeptr drr(nodeptr &); 
int max(int,int); int nonodes(nodeptr); 
}; 
// Inserting a node 
void bstree::insert(int x,nodeptr &p) 
{ 
if (p == NULL) 
{ 
p = new node; 
p->element = x; 
p->left=NULL; 
p->right = NULL; 
p->height=0; 
if (p==NULL) 
cout<<"Out of Space"; 
} 
else 
{ 
if (x< p-> element) 
{ 
insert(x,p->left); 
if ((bsheight(p->left) - bsheight(p->right))==2) 
{ if (x < p->left->element) 
p=srl(p); 
else 
p = drl(p); 
} 
} 
else if (x>p->element) 
{ insert(x,p->right); 
if ((bsheight(p->right) - bsheight(p->left))==2) 
{ 
if (x > p->right->element) 
p=srr(p); 
else 
p = drr(p); 
} 
} else 
cout<<"Element Exists"; 
} 
int m,n,d; 
m=bsheight(p->left); 
n=bsheight(p->right); 
d=max(m,n); 
p->height = d + 1; 
} 
// Finding the Smallest 
nodeptr bstree::findmin(nodeptr p) 
{ 
if (p==NULL) 
{ cout<<"Empty Tree"; 
return p; } 
else 
{ 
while(p->left !=NULL) 
p=p->left; 
return p; 
} 
} 
// Finding the Largest 
nodeptr bstree::findmax(nodeptr p) 
{ 
if (p==NULL) 
{ 
cout<<"Empty Tree"; return p; 
} else 
{ while(p->right !=NULL) 
p=p->right; 
return p; 
} } 
// Finding an element 
void bstree::find(int x,nodeptr &p) 
{ 
if (p==NULL) 
cout<<"Element not found"; 
else 
if (x < p->element) 
find(x,p->left); else 
if (x>p->element) 
find(x,p->right); 
else 
cout<<"Element found !"; 
} 
// Copy a tree void bstree::copy(nodeptr &p,nodeptr &p1) 
{ 
makeempty(p1); 
p1 = nodecopy(p); 
} 
// Make a tree empty 
void bstree::makeempty(nodeptr &p) 
{ nodeptr d; 
if (p != NULL) 
{ 
makeempty(p->left); 
makeempty(p->right); 
d=p; 
free(d); p=NULL; 
} } 
// Copy the nodes 
nodeptr bstree::nodecopy(nodeptr &p) 
{ 
nodeptr temp; 
if (p==NULL) 
return p; 
else 
{ 
temp = new node; 
temp->element = p->element; 
temp->left = nodecopy(p->left); 
temp->right = nodecopy(p->right); 
return temp; } 
} 
// Deleting a node void bstree::del(int x,nodeptr &p) 
{ 
nodeptr d; 
if (p==NULL) 
cout<<"Element not found "; 
else if ( x < p->element) 
del(x,p->left); 
else if (x > p->element) 
del(x,p->right); 
else if ((p->left == NULL) && (p->right == NULL)) 
{ 
d=p; 
free(d); 
p=NULL; 
cout<<"Element deleted !"; } 
else if (p->left == NULL) 
{ 
d=p; 
free(d); p=p->right; 
cout<<"Element deleted !"; 
} 
else if (p->right == NULL) 
{ 
d=p; 
p=p->left; 
free(d); 
cout<<"Element deleted !"; } 
else 
p->element = deletemin(p->right); 
} 
int bstree::deletemin(nodeptr &p) 
{ 
int c; cout<<"inside deltemin "; 
if (p->left == NULL) 
{ 
c=p->element; 
p=p->right; 
return c; 
} else 
{ 
c=deletemin(p->left); 
return c; 
} 
} 
void bstree::preorder(nodeptr p) 
{ if (p!=NULL) 
{ cout<< p-> element <<"-->"; 
preorder(p->left); 
preorder(p->right); 
} 
} 
// Inorder Printing 
void bstree::inorder(nodeptr p) 
{ 
if (p!=NULL) 
{ 
inorder(p->left); 
cout<< p->element <<"-->"; 
inorder(p->right); 
} 
} // PostOrder Printing 
void bstree::postorder(nodeptr p) 
{ 
if (p!=NULL) 
{ 
postorder(p->left); 
postorder(p->right); 

cout<< p->element<<"-->"; } 
} int bstree::max(int value1, int value2) 
{ 
return ((value1 > value2) ? value1 : value2); 
} 
int bstree::bsheight(nodeptr p) 
{ 
int t; 
if (p == NULL) 
return -1; 
else { 
t = p->height; 
return t; 
} 
} 
nodeptr bstree:: srl(nodeptr &p1) 
{ 
nodeptr p2; 
p2 = p1->left; 
p1->left = p2->right; 
p2->right = p1; 
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1; 
p2->height = max(bsheight(p2->left),p1->height) + 1; 
return p2; 
} 
nodeptr bstree:: srr(nodeptr &p1) 
{ 
nodeptr p2; 
p2 = p1->right; 
p1->right = p2->left; 
p2->left = p1; 
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1; 
p2->height = max(p1->height,bsheight(p2->right)) + 1; 
return p2; 
} 
nodeptr bstree:: drl(nodeptr &p1) 
{ 
p1->left=srr(p1->left); return srl(p1); 
} 
nodeptr bstree::drr(nodeptr &p1) 
{ 
p1->right = srl(p1->right); 
return srr(p1); } 
int bstree::nonodes(nodeptr p) 
{ 
int count=0; 
if (p!=NULL) 

{ nonodes(p->left); 
nonodes(p->right); count++; 
} 
return count; 
} int main() 
{ clrscr(); 
nodeptr root,root1,min,max;//,flag; 
int a,choice,findele,delele,leftele,rightele,flag; 
char ch='y'; 
bstree bst; 
//system("clear"); 
root = NULL; 
root1=NULL; 
cout<<"AVL Tree"; 
cout<<"========"; 
do 
{ 
cout<<" 
1.Insertion 
2.FindMin "; 
cout<<"3.FindMax 
4.Find 
5.Copy "; 
cout<<"6.Delete 
7.Preorder 
8.Inorder "; 
cout<<"9.Postorder 
10.height "; 
cout<<"Enter the choice:"; 
cin>>choice; 
switch(choice) 
{ 
case 1: 
cout<<"New node's value ?"; 
cin>>a; 
bst.insert(a,root); 
break; 
case 2: 
if (root !=NULL) 
{ 
min=bst.findmin(root); 
cout<<"Min element : "<< min->element; 
} 
break; case 3: 
if (root !=NULL) 
{ 
max=bst.findmax(root); 
cout<<"Max element : "<< max->element; 
} 
break; case 4: 
cout<<"Search node : "; 
cin>>findele; 
if (root != NULL) 
bst.find(findele,root); 
break; 
case 5: 
bst.copy(root,root1); 
bst.inorder(root1); 
break; 
case 6: 
cout<<"Delete Node ?"; 
cin>>delele; 
bst.del(delele,root); 
bst.inorder(root); break; 
case 7: 
cout<<"Preorder Printing... :"; 
bst.preorder(root); 
break; 
case 8: 
cout<<"Inorder Printing.... :"; 
bst.inorder(root); break; 
case 9: 
cout<<"Postorder Printing... :"; 
bst.postorder(root); 
break; 
case 10: 
cout<<"Height and Depth is "; 
cout<< bst.bsheight(root); 
cout<<"No. of nodes:- "<< bst.nonodes(root); 
break; 
}
cout<<"Do u want to continue (y/n) ?"; 
cin>>ch; 
}
while(ch=='y'); 
return 0; }
} 
cout<<"Continue (y/n) ?"; 
cin>>c; 
}
while (c=='y' || c == 'Y'); 
return 0; 
}