//ARRAY MANIPULATION
#include<iostream>
#include<math.h>
using namespace std;
void maxx(int*,int);
int main(){
	int n,f,s,m;
	int a[100];
	cout<<"Enter the number of elements in array : ";
	cin>>n;
	int arr[n];
	int arr2[n];
	double arr1[n];
	double avg=0,Md=0;
	for(int i=0;i<n;i++){
		cin>>arr[i];
		arr2[i]=arr[i];
	}
	for(int i=0;i<n;i++){
		avg=avg+arr[i];
	}
	avg=avg/n;
	cout<<"Mean : "<<avg<<endl;
	for(int i=0;i<n;i++){
		arr1[i]=arr[i]-avg;
		arr1[i]=arr[i]*arr1[i];
		Md=Md+arr1[i];
	}
	Md=Md/n;
	Md=sqrt(Md);
	cout<<"Mean Deviation : "<<Md;
	maxx(&arr[0],n);
	cout<<"enter the number to be searched : ";
	cin>>f;
	cout<<"Position of the number: ";
	for(int i=0;i<n;i++){
		if(arr2[i]==f){
			cout<<i<<",";
		}
	}

	cout<<endl<<"Enter the index of the number to be deleted : ";
	cin>>f;
	if(f<n){
	   for(int i=0;i<f;i++){
		arr2[i]=arr2[i];
	   }
	    for(int i=f;i<n-1;i++){
		arr2[i]=arr2[i+1];
		}

	    for(int i=0;i<n-1;i++){
		cout<<endl<<arr2[i];
	    }
    }
    else{
    	cout<<"Index is out of Range.";
	}
	cout<<endl;

	cout<<"enter a number to check: ";
	cin>>s;
	cout<<endl;
	for(int i=0;s!=0;i++){
		a[i]=s%10;
		s=s/10;
		m=i+1;
	}
	for(int i=0;i<m;i++){
		cout<<a[i];
	}
	for(int i=0;i<(m+1)/2;i++){
		if(a[i]==a[m-i-1]){
			if(i==(m-1)/2){
				cout<<endl<<"number is palindrome number.";
				break;
			}
		}
		else{
			cout<<endl<<"number is not palindrome number";
			break;
		}
	}
		return 0;
}
void maxx(int *a,int n){
	int temp;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(a[i]>a[j]){
			temp=a[j];
			a[j]=a[i];
			a[i]=temp;
		    }
		}
	}
	cout<<endl<<"Max elements : "<<a[n-1]<<endl<<"Min element :"<<a[0]<<endl;
}




//PALINDROME

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
	int i,j,l,c=0;
	char s[20];
	cout<<"Enter a string :-";
	cin>>s;
	l=strlen(s);
	for(i=0,j=l-1;i<l;i++,j--)
	{
		if(s[i]!=s[j])
		{
			cout<<"Not a Palindorme string.";
			c++;
			break;
		}
	}
	if(c==0)
		cout<<"Palindrome string.";
return 0;
}


//MATRIX MANIPULATION
#include<bits/stdc++.h>
using namespace std;
int main(){
	int arr1[3][3];
	int arr2[3][3];
	int add[3][3];
	int sub[3][3];
	int mul[3][3];
	int n;
	cout<<"enter the elements of Matrix 1: ";
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			cin>>arr1[i][j];
		}
	}

	cout<<"enter the elements of Matrix 2: ";
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			cin>>arr2[i][j];
		}
	}

	cout<<"The sum of Matrix 1 & 2: \n";
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			add[i][j]=arr1[i][j]+arr2[i][j];
			cout<<add[i][j]<<"\t";
		}
		cout<<endl;
	}

	cout<<endl<<"The subtraction of Matrix 1 & 2: \n";
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			sub[i][j]=arr1[i][j]-arr2[i][j];
			cout<<sub[i][j]<<"\t";
		}
		cout<<endl;
	}

	cout<<"The multiplication of Matrix 1 & 2: \n";
	for(int i=0;i<3;i++){
		int sum=0;
		for(int j=0;j<3;j++){
	        for(int k=0;k<3;k++){
	        	sum=sum+arr1[i][k]*arr2[k][j];
			}
			mul[i][j]=sum;
			cout<<mul[i][j]<<"\t";
		}
		cout<<endl;
	}
	return 0;
}

//MERGE TWO SORTED ARRAYS INTO ONE.
#include<iostream>
using namespace std;
int main(){
	int a[10],b[10], c[10], i=0,temp,j;
	cout<<"Enter the elements of first array:-\n";
	for(i=0;i<5;i++)
	{
		cin>>a[i];
	}
	cout<<"Enter the elements of second array :-\n";
	for(i=0;i<5;i++)
	{
		cin>>b[i];
	}
	//sorting arrays
	for(i=1;i<5;i++){
		for(j=0;j<5;j++){
			if(a[i]<a[j]){
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
			if(b[i]<b[j]){
				temp=b[i];
				b[i]=b[j];
				b[j]=temp;
                                            }
		}
	}
	cout<<"First sorted array:-\n";
	for(i=0;i<5;i++){
		cout<<a[i]<<" ";
	}
	cout<<"\nSecond sorted array:-\n";
	for(i=0;i<5;i++){
		cout<<b[i]<<" ";
	}
	for(i=0;i<5;i++){
		c[i]=a[i];
		c[i+5]=b[i];
	}
	//Sorting merged arrays
	for(i=1;i<10;i++){
		for(j=0;j<10;j++){
			if(c[i]<c[j]){
				temp=c[i];
				c[i]=c[j];
				c[j]=temp;
			}
		}
	}
	cout<<"\nMerged Sorted array:\n";
	for(i=0;i<10;i++){
		cout<<c[i]<<" ";
	}
return 0;
}



//STACK BASICS
#include<iostream>
#define MAX 5
int top,status;
using namespace std;
void push(int stack[], int item){
	if(top==(MAX-1))
		status=0;
	else {
	          status =1;
                 top++;
      	          stack[top]=item;
	          }
}
int pop(int stack[]){
	int ret;
	if(top==-1){
		ret=0;
		status=0;
	}
	else{
	       status=1;
	       ret=stack[top];
	       --top;
   	}
return ret;
}
void display(int stack[]){
	int i;
	cout<<"The Stack is :";
	if(top==-1)
		cout<<"empty\n";
	else{
            	cout<<endl;
		for(i=top;i>=0;--i)
			cout<<stack[i]<<endl;
		cout<<endl;
       }
}
int main(){
	int stack[MAX],item,ch;
	top=-1;
	do{
		do{
			cout<<"\nMain Menu\n"<<"1.Push an element.\n"<<"2.Pop an element.\n"<<"3.Exit!\n"<<"Enter your choice :-";
			cin>>ch;
			if(ch<1 || ch>3)
				cout<<"\nInvalid Choice, Please try again!!";
		}while(ch<1 || ch>3);
	switch(ch)	{
		case 1:
			cout<<"Enter the element to be pushed :-";
			cin>>item;
			push(stack,item);
			if (status){
                	 cout<<"\nAfter Pushing ";
		   		 display (stack);
		    		if (top == (MAX-1))
				cout<<"\nThe Stack is Full";
			}
			else
				cout<<"\nStack overflow on Pushn\n";
			break;
       case 2:
		item = pop (stack);
		if (status){
          cout<<"\After Popping: ";
		     	display (stack);
}
		else
			cout<<"\nStack underflow on Pop\n";
		break;
       default:
		cout<<"\nEND OF EXECUTION";
       }
}while (ch != 3);
return 0;
}


//INFIX TO POSTFIX
#include <iostream>
#include <stack>
#include <string>
using namespace std;
void print(stack<char>&stk);
int main(){
	stack<char>stk;
	string S;
	cin>> S;
	S = '(' + S + ')';
	for(int i = 0; i <S.length(); i++){
		if(S[i] == '(')
			stk.push(S[i]);
		else if(S[i] == '+' || S[i] == '-'){
			if(stk.top() == '*' || stk.top() == '/' || stk.top() == '^')
				print(stk);
			stk.push(S[i]);
}
		else if(S[i] == '*' || S[i] == '/'){
			if(stk.top() == '^')
				print(stk);
			stk.push(S[i]);
		}
		else if(S[i] == '^')
			stk.push(S[i]);
		else if(S[i] == ')')	{
			print(stk);
			stk.pop();
		}
		else
			cout<< S[i];
	}
return 0;
}
void print(stack<char>&stk){
	while(stk.top() != '(')
		std::cout<<stk.top(), stk.pop();
}

//POSTFIX EVALUATION
#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
int main()
{	int i=0,c,a,b,len;
	stack<int>stk;
	string p;
	cout<<"Enter a postfix expression:- ";
	cin>>p;
	for(i=0;i<p.length();i++)
	{	if(p[i]=='+' || p[i]=='-' || p[i]=='*' || p[i]=='/')
		{
			b=stk.top();
			stk.pop();
			a=stk.top();
			stk.pop();
			if(p[i]=='+')
				c=a+b;
			else if(p[i]=='-')
				c=a-b;
			else if(p[i]=='*')
				c=a*b;
			else if(p[i]=='/')
				c=a/b;
			stk.push(c);
		}
		else{
			int t = p[i] - '0';
			stk.push(t);
		}
	}
	cout<<stk.top();
return 0;
}

//FIBONACCI (RECURSIVE)
#include<iostream>
using namespace std;
int fib(int );
int main(){
	int n;
	cout<<"enter the length of series : ";
	cin>>n;
	for(int i=0;i<n;i++){
		cout<<fib(i)<<"\t";
	}
return 0;
}
int fib(int n){
	int f;
	if(n==0||n==1){
		return 1;
	}
	else{
		f=fib(n-1)+fib(n-2);
		return f;
	}
}

//FIBONACCI (NON-RECURSIVE)
#include<iostream>
using namespace std;
void fib(int );
int main(){
	int n;
	cout<<"Enter the length of series : ";
	cin>>n;
	fib(n);
	return 0;
}
void fib(int n){
	int i;
	int temp;
	int x=0;
	int y=1;
	if(n==1){
		cout<<n<<"\t";
	}
	else{
		cout<<"1"<<"\t";
			for(i=2;i<=n;i++){
			cout<<x+y<<"\t";
			temp=y;
			y=x+y;
			x=temp;
		}
	}
}

// Swap 2 top elements of a stack.
#include<iostream>
using namespace std;
class stck{
	int stack[10];
	int tos=-1;
	public:
	void push(int x){
		if(tos==9){
			cout<<"stack is full.\n";
		}
		else{
			tos=tos+1;
			stack[tos]=x;
		}
	}
	int pop(){
		int x;
		if(tos<0){
			cout<<"stack is empty.\n";
		}
		else{
			x=stack[tos];
			tos=tos-1;
			return x;
		}
	}
	void swap(){
		int x,y;
		x=pop();
		y=pop();
		push(x);
		push(y);
	}
	void print(){
		for(int i=0;i<=tos;i++){
			cout<<stack[i]<<"\t";
		}
	}
};
int main(){
	stck s;
	int n,m;
	cout<<"number of elements to be pushed : ";
	cin>>m;
	cout<<"NUMBERS -- ";
	for(int i=0;i<m;i++){
		cin>>n;
		s.push(n);
	}
	s.print();
	cout<<endl;
	cout<<"After swap"<<endl;
	s.swap();
    s.print();
	return 0;
}



//REVERSE THE STACK
#include<iostream>
#include<stack>
using namespace std;
int main(){
	stack<int>s,r;
	int n;
	cout<<"Enter the size of stack--   ";
	cin>>n;
	cout<<"Enter the elements -- ";
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		s.push(x);
	}
	cout<<endl<<"After reversing numbers --"<<"\t";
	for(int i=0;i<n;i++){
		int z;
		z=s.top();
		r.push(z);
		s.pop();
	}
	for(int i=0;i<n;i++){
		cout<<r.top();
		r.pop();
		cout<<"\t";
	}
	return 0;
}


//QUEUE(INSERT AND DELETE)
#include<iostream>
using namespace std;
#define MAX 50
int q[MAX];
int display();
int insert();
int del();
int search();
int menu();
int rear = - 1;
int front = - 1;
int main()
{
	int c;
	while(1){
		cout<<"\n1.Insert an element\n2. Delete an element\n3. Search an element\n4. Display the queue\n5.Exit \nEnter your choice: ";
		cin>>c;
		if(c==1)
			insert();
		if(c==2)
			del();
		if(c==3)
			search();
	    	if(c==4)
			display();
	    	if(c==5)
			exit(1);
		else if(c<1 || c>5)
			cout<<"Invalid Choice";
	}
	return 0;
}
insert(){
	int add_item;
    if (rear == MAX - 1)
		cout<<"Queue Overflow \n";
    else{
	    if (front == - 1)
        	front = 0;
		cout<<"Insert the element in queue : ";
		cin>>add_item;
        rear = rear + 1;
        q[rear] = add_item;
    }
cout<<endl;
}
del(){
	if (front == - 1 || front > rear){
	    cout<<"\n\n\tQueue Underflow \n\n";
		return 0 ;
	}
    else{
	    cout<<"\n\nElement deleted from queue is :"<<q[front]<<"\n\n";
        front = front + 1;
    }
}
display(){
	int i;
    if (front == - 1)
		cout<<"Queue is empty \n";
    else{
		cout<<"\n\n\tQueue is : \n\t";
        for (i = front; i <= rear; i++)
			cout<<q[i]<<" ";
		cout<<"\n\n";
    }
}
search(){
	int i,s,x=0;
	cout<<"Enter the element to be searched:";
	cin>>s;
	for(i=front;i<=rear;i++){
		if(q[i]==s)
		cout<<"\n\tElement is present in the queue\n\n";
		else
		x++;
	}
	if(x==1)
		cout<<"\n\tElement is not present in the queue!\n\n";
}

//QUEUE WITH TWO STACKS
#include<iostream>
#include<stack>
using namespace std;
class queue {
   stack<int> s1, s2;
public  :
   void enqueue(int element);
   int dequeue();
   void displayQueue();
};
void queue :: enqueue(int element) {
   s1.push(element);
}
int queue :: dequeue() {
   while (!s1.empty()) {
      s2.push(s1.top());
      s1.pop();
   }
   int ret = s2.top();
   s2.pop();
   while (!s2.empty()) {
      s1.push(s2.top());
      s2.pop();
   }
   return ret;
}
void queue :: displayQueue() {
   cout<<"\nDisplaying the queue :-\n";
   while (!s1.empty()) {
      s2.push(s1.top());
      s1.pop();
   }
   while (!s2.empty()) {
      cout<<s2.top()<<" ";
      s1.push(s2.top());
      s2.pop();
   }
}
int main() {
   queue q;
   q.enqueue(5);
   q.enqueue(11);
   q.enqueue(1);
   q.enqueue(7);
   q.enqueue(13);
   q.enqueue(11);
   q.displayQueue();
   int dq_element = q.dequeue();
   cout<<"\nAfter dequeing :-";
   q.displayQueue();
   cout<<endl;
   return 0;
}


//LINKED LIST
//NODE BEFORE LAST NODE
#include<iostream>
using namespace std;
void insert(int);
void print(void);
int printadd_before_last_element();
class node{
	public:
	int data;
	node *next;
};
node *head;
int main(){
	int n,x;
	cout<<"Enter the total number to be inserted in the linklist-- ";
	cin>>n;
	for(int i=0;i<n;i++){
		cout<<"Enter the number -- ";
		cout<<endl;
		cin>>x;
		insert(x);
	}
	cout<<"\nList:  "<<"\n";
	print();
	cout<<"Address of element before last element -- ";
	printadd_before_last_element();
	return 0;
}


void insert(int x){
	node *temp=new node();
	node *temp1;
	temp1=head;
	temp->data=x;
	temp->next=NULL;
	if(head==NULL){
		head=temp;
	}
	else{
		while(temp1->next!=NULL){
			temp1=temp1->next;
		}
		temp1->next=temp;
	}
}
void print()
{
	node *temp=head;
	while(temp!=NULL){
		cout<<temp->data<<"\t";
		temp=temp->next;
	}
	cout<<"\n\n";
}
int printadd_before_last_element(){
	node* s1=head;
	node* s2;
	if(s1==NULL)
		return 0;
	if(s1->next==NULL)
		return 0;
	while(s1->next!=NULL){
		s2=s1;
		s1=s1->next;
	}
	cout<<s2;
}


//DOUBLE LINKED LIST
#include<iostream>
using namespace std;
void insatbeg(int);
void insatend(int);
void del_beg();
void del_end();
void display();
struct node
{	int data;
	struct node *pre, *nex;
}
*head=NULL;
int main(){
	int choice,val;
	while(1)
	{	cout<<"\n"<<"1. Insert at begining \n"<<"2. Insert at end\n"<<"3.Delete at begining\n"<<"4.Delete at end\n"<<"5.display\n"<<"6.Exit\n";
		cin>>choice;
		switch(choice)
		{	case 1:
				cout<<"Enter the value to be inserted :-";
				cin>>val;
				insatbeg(val);
				break;
			case 2:
				cout<<"Enter the value to be inserted :-";
				cin>>val;
				insatend(val);
				break;
			case 3:
				del_beg();
				break;
			case 4:
				del_end();
				break;
			case 5:
				display();
				break;
			case 6:
				exit(1);
		}
		cout<<endl;
	}
return 0;
}
void insatbeg(int x)
{	struct node *newNode= new node();
	newNode->data=x;
	newNode->pre =NULL;
	if(head==NULL)
	{	newNode->nex= NULL;
		head = newNode;
	}
	else
	{	newNode->nex=head;
		head = newNode;
	}
	cout<<"Inerted Successfully!"<<endl;
}

void insatend(int x)
{	struct node *newNode = new node();
	newNode->data=x;
	newNode->nex=NULL;
	if(head==NULL)
	{	newNode->pre=NULL;
		head=newNode;
	}
	else
	{	struct node *temp=head;
		while(temp->nex!=NULL)
		{	temp=temp->nex;
		}
		temp->nex=newNode;
		newNode->pre=temp;
	}
	cout<<"Inesertion successful!"<<endl;
}
void del_beg(){
	if(head==NULL){
		cout<<endl<<"List is empty deletion not possible!"<<endl;
		return ;
	}
	else{
		node *temp=head;
		if(temp->pre==temp->nex){
			head=NULL;
		}
		else{
		head=temp->nex;
		head->pre=NULL;
		}
		display();
	}
}
void del_end()
{	if(head==NULL)
		cout<<endl<<"List is Empyt!!!Deletion is not possible."<<endl;
	else{	node *temp=head;
		if(temp->pre==NULL && temp->nex==NULL)
		{	head=NULL;

		}
		else{
			while(temp->nex->nex!=NULL)
			{	temp=temp->nex;
			}
			temp->nex=NULL;
		}
	display();
	}
}
void display()
{	if(head==NULL)
	{	cout<<endl<<"List is empty!"<<endl<<endl;
		return;
	}
	else{
		node *temp=head;
		cout<<endl;
		cout<<"NULL <--";
		while(temp->nex!=NULL)
		{	cout<<temp->data<<"<===>";
			temp=temp->nex;
		}	cout<<temp->data<<" --> NULL";
	}	cout<<endl<<endl;
}
// circular single linked list.
	#include<iostream>
using namespace std;
void insert(int);
void del();
void display();
struct node{
	int data;
	struct node *next;
}*head=NULL;
int main()
{	while(1)
	{	int choice, val;
		cout<<"Menu: \n"<<"1.Insert\n"<<"2.Delete\n"<<"3.Display\n"<<"4.Exit\n";
		cin>>choice;
		switch(choice)
		{	case 1:
				cout<<"Enter the value to be inserted :-";
				cin>>val;
				insert(val);
				break;
			case 2:
				del();
				break;
			case 3:
				display();
				break;
			case 4:
				exit(1);
		}
		cout<<endl;
	}
return 0;
}
void insert(int x){
	struct node *newNode = new node();
	newNode->data=x;
	if(head==NULL){
		head=newNode;
		newNode->next=head;
	}
	else{
		node *temp=head;
		while(temp->next!=head){
			temp=temp->next;
		}
		newNode->next=head;
		head=newNode;
		temp->next=head;
	}
	cout<<endl;
}
void del(){
	if(head==NULL){
		cout<<"List is empty!";
	}
	else{
		struct node *temp1=head;
		struct node *temp2=head;
		if(temp1->next==head){
			head==NULL;
		}
		else{
			while(temp1->next!=head){
				temp1=temp1->next;
			}
			head=temp2->next;
			temp1->next=head;
		}
	display();
       }
}
void display(){
	if(head==NULL){
		cout<<"\nList is empty!\n";
	}
	else{
		struct node *temp=head;
		while(temp->next!=head){
			cout<<temp->data<<"-->";
			temp=temp->next;
		}
		cout<<temp->data<<"-->"<<head->data;
                                       }
}

// inorder, preorder and postorder binary tree traversal.
//Write a program to insert ,find, min, max in a binary tree.
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node{
	struct node *lchd;
	int data;
	struct node *rchd;
};
const int MAX=10;
struct node *stack[MAX];
int top=-1;
void push_stack(struct node *item){
	if(top==(MAX-1)){
		cout<<"stack overflow."<<endl;
	}
	else{
	top=top+1;
	stack[top]=item;
	}
}
struct node* pop_stack(){
	struct node *item;
	if(top==-1){
		cout<<"stack is empty"<<endl;
	}
	else{
		item=stack[top];
		top--;
		return item;
	}
}
int stack_empty(){
	if(top==-1)
		return 1;
	else
		return 0;
}
void pre(struct node *root){
	struct node *ptr =root;
	if(ptr==NULL){
		cout<<"Tree is empty.";
		return;
	}
	push_stack(ptr);
	while(!stack_empty()){
		ptr=pop_stack();
		cout<<ptr->data<<endl;
		if(ptr->rchd!=NULL){
			push_stack(ptr->rchd);
		}
		if(ptr->lchd!=NULL){
	//		cout<<ptr->data;
			push_stack(ptr->lchd);
		}
	}
}
void in(struct node *root){
	struct node *ptr=root;
	if(ptr==NULL){
		cout<<"stack is empty"<<endl;
		return;
	}
	while(1){
		while(ptr->lchd!=NULL){
			push_stack(ptr);
			ptr=ptr->lchd;
		}
		while(ptr->rchd==NULL){
			cout<<ptr->data<<endl;
			if(stack_empty()){
				return;
			}
			ptr=pop_stack();
		}
		cout<<ptr->data<<endl;
		ptr=ptr->rchd;
	}
	cout<<endl;
}
void post(struct node *root){
	struct node *ptr,*q;
	ptr=root;
	if(ptr==NULL){
		cout<<"stack is empty"<<endl;
		return;
	}
	q=root;
	while(1){
		while(ptr->lchd!=NULL){
			push_stack(ptr);
			ptr=ptr->lchd;
		}
		while(ptr->rchd==NULL||ptr->rchd==q){
			cout<<ptr->data<<endl;
			q=ptr;
			if(stack_empty())
				return;
			ptr=pop_stack();
		}
		push_stack(ptr);
		ptr=ptr->rchd;
	}
	cout<<endl;
}
struct node* search(struct node* root, int value){
    if (root == NULL || root->data == value)
       return root;
	if (root->data<value)
       return search(root->rchd,value);
    if(root->data>value)
    	return search(root->lchd,value);
}
struct node* newNode(int item)
{
    struct node *temp =  (struct node *)malloc(sizeof(struct node));
    temp->data = item;
    temp->lchd = NULL;
	temp->rchd = NULL;
    return temp;
}
struct node* insert(struct node* node,int value){
	if(node==NULL){
		return newNode(value);
	}
	if(value<node->data){
		node->lchd=insert(node->lchd,value);
	}
	else if(value>node->data){
		node->rchd=insert(node->rchd,value);
	}
	return node;
}
struct node* search_min(struct node* root){
	if(root->lchd==NULL){
		return root;
	}
	else{
		search_min(root->lchd);
	}
}
struct node* search_max(struct node* root){
	if(root->rchd==NULL){
		return root;
	}
	else{
		search_max(root->rchd);
	}
}
bool search_tree(struct node* root, int value){
	struct node *temp =  (struct node *)malloc(sizeof(struct node));
	temp=search(root,value);
	cout<<"searching for "<<value<<" node."<<endl;
	if(temp!=NULL){
		cout<<"node is in binary tree."<<endl;
		return true;
	}
	else{
		cout<<"node is not in binary tree."<<endl;
		return false;
	}
}
int main(){
	struct node *root=NULL;
	int value;
	root=insert(root,30);
	insert(root,50);
	insert(root,40);
	insert(root,20);
	insert(root,10);
	insert(root,5);
	insert(root,15);
	insert(root,45);

	cout<<"inorder"<<endl;
	in(root);
	cout<<"preorder"<<endl;
	pre(root);
	cout<<"postorder"<<endl;
	post(root);
	cout<<"Enter the data of node to be search -- ";
	cin>>value;
	search_tree(root,value);
	cout<<"Enter the data of node to be search -- ";
	cin>>value;
	search_tree(root,value);
	cout<<"Maximum node -- "<<search_max(root)->data<<endl;
	cout<<"Minimum node -- "<<search_min(root)->data;
	return 0;
}


// AVL TREE
#include<iostream>
#include<stdlib.h>
using namespace std;
struct Node{
    int key;
	struct Node *left;
	struct Node *right;
	int height;
};
int max(int a, int b);
int height(struct Node *N)
{    if (N == NULL)
        return 0;
    return N->height;
}
int max(int a, int b){
    return (a > b)? a : b;
}
struct Node* newNode(int key){
    struct Node* node = new Node;
    node->key   = key;
    node->left   = NULL;
	node->right  = NULL;
    node->height = 1;
    return(node);
}
struct Node *rightRotate(struct Node *y){
    struct Node *x = y->left;
	struct Node *T2 = x->right;
    x->right = y;
    y->left = T2;
	y->height = max(height(y->left), height(y->right))+1;
	x->height = max(height(x->left), height(x->right))+1;
    return x;
}
struct Node *leftRotate(struct Node *x){
    struct Node *y = x->right;
	struct Node *T2 = y->left;
    y->left = x;
    x->right = T2;
	x->height = max(height(x->left), height(x->right))+1;
	y->height = max(height(y->left), height(y->right))+1;
    return y;
}
int getBalance(struct Node *N)
{    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
struct Node* insert(struct Node* node, int key)
{
    /* 1.  Perform the normal BST insertion */
    if (node == NULL)
        return(newNode(key));
     if (key < node->key)
node->left  = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else // Equal keys are not allowed in BST
        return node;
     /* 2. Update height of this ancestor node */
    node->height = 1 + max(height(node->left),
                           height(node->right));
     /* 3. Get the balance factor of this ancestor
          node to check whether this node became
          unbalanced */
int balance = getBalance(node);
     // If this node becomes unbalanced, then
    // there are 4 cases
     // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
     // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
     // Left Right Case
    if (balance > 1 && key > node->left->key)
    {     node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
    // Right Left Case
    if (balance < -1 && key < node->right->key)
    {        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    /* return the (unchanged) node pointer */
    return node;
}
// A utility function to print preorder traversal
// of the tree.
// The function also prints height of every node
void preOrder(struct Node *root)
{
if(root != NULL)
    {
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
    }
}
/* Drier program to test above function*/
int main()
{
struct Node *root = NULL;
  /* Constructing tree given in the above figure */
root = insert(root, 20);
root = insert(root, 10);
root = insert(root, 30);
root = insert(root, 50);
root = insert(root, 40);
root = insert(root, 25);
cout<<"Preorder traversal of AVL tree is \n";
preOrder(root);
  return 0;
}


//SORTING PROGRAMS
Insertion Sort & Selection Sort –
#include<iostream>
using namespace std;
#define Max 100
void insertion_sort(int *,int);
void selection_sort(int *,int);
int main(){
	int arr[Max],n,ch;
	cout<<"Enter the number of elements -- ";
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	cout<<"1.insertion_sort.\n"<<"2.selection_sort.\n”<<"4.exit\n";
	cin>>ch;
	switch(ch){
		case 1:
			insertion_sort(arr,n);
			break;
		case 2:
			selection_sort(arr,n);
			break;
		case 3:
			exit(1);
	}
	cout<<"sorted list is --";
	for(int i=0;i<n;i++){
		cout<<*(arr+i)<<" ";
	}
	cout<<endl;
	return 0;
}
void insertion_sort(int *arr,int n){
	int k,j;
	for(int i=1;i<n;i++){
		k=*(arr+i);
		for( j=i-1;j>=0&&(k<*(arr+j));j--)
			*(arr+j+1)=*(arr+j);
		*(arr+j+1)=k;
	}
}
void selection_sort(int *arr,int n){
	int min,temp;
	for(int i=0;i<n-1;i++){
		min =i;
		for(int j=i+1;j<n;j++){
			if(*(arr+min)>*(arr+j))
				min=j;
		}
		if(i!=min){
			temp=*(arr+i);
			*(arr+i)=*(arr+min);
			*(arr+min)=temp;
		}
	}
}
//Bubble Sort:
#include<iostream>
using namespace std;
int main()
{
int a[50],n,i,j,temp;
cout<<"Enter the size of array: ";
cin>>n;
cout<<"Enter the array elements: ";

for(i=0;i<n;++i)
cin>>a[i];

for(i=1;i<n;++i)
    {
for(j=0;j<(n-i);++j)
            if(a[j]>a[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
a[j+1]=temp;
            }
    }

cout<<"Array after bubble sort:";
for(i=0;i<n;++i)
cout<<" "<<a[i];

    return 0;
}


//Quick Sort:
#include <iostream>
using namespace std;
voidquick_sort(int[],int,int);
int partition(int[],int,int);
int main()
{
int a[50],n,i;
cout<<"How many elements?";
cin>>n;
cout<<"\nEnter array elements:";
for(i=0;i<n;i++)
cin>>a[i];
quick_sort(a,0,n-1);
cout<<"\nArray after sorting:";
for(i=0;i<n;i++)
cout<<a[i]<<" ";
    return 0;
}
Void quick_sort(int a[],intl,int u)
{    int j;
    if(l<u)
    {        j=partition(a,l,u);
quick_sort(a,l,j-1);
quick_sort(a,j+1,u);
    }
}
int partition(int a[],intl,int u)
{
intv,i,j,temp;
    v=a[l];
    i=l;
    j=u+1;
    do
    {
        do
            i++;
        while(a[i]<v&&i<=u);
        do
            j--;
        while(v<a[j]);
                if(i<j)
        {    temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
}while(i<j);
    a[l]=a[j];
    a[j]=v;
    return(j);
}


//Merge Sort:
#include<iostream>
using namespace std;
void merge_sort(int [],int ,int );
void merge(int [],int,int ,int );
int main()
{
int n;
cout<<"Enter the size of the array"<<endl;
cin>>n;
int a[n];
cout<<"Enter the elements in the array"<<endl;
for(int i=1;i<=n;i++)
    {
cin>>a[i];
    }
cout<<"sorting using merge sort"<<endl;
int p=1,r=n;
merge_sort(a,p,r);
cout<<"sorted form"<<endl;
for(int i=1;i<=n;i++)
   {
cout<<"a["<<i<<"]="<<a[i]<<endl;
   }
     return 0;
}
void merge_sort(int a[],int p,int r)
    {
int q;
        if(p<r)
        {
         q=(p+r)/2;
merge_sort(a,p,q);
merge_sort(a,q+1,r);
merge(a,p,q,r);
        }
    }
void merge(int a[],int p,int q,int r)
    {
cout<<"Entered merge"<<endl;
int n1=q-p+1;
int n2=r-q;
int L[n1+1];
int R[n2+1];
for(int i=1;i<=n1;i++)
        {
            L[i]=a[p+i-1];
        }
for(int j=1;j<=n2;j++)
        {
            R[j]=a[q+j];
        }
L[n1+1]=999;
R[n2+1]=999;
int i=1, j=1;
for(int k=p;k<=r;k++)
        {
            if(L[i]<=R[j])
            {
                a[k]=L[i];
                i=i+1;
            }
            else
            {
                a[k]=R[j];
                j=j+1;
            }
        }
    }