/* binary search tree */
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>

typedef struct link {
   int data;
   struct link *lchild, *rchild;
} node;

void insert(node *, node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *, int, node **);

void main() {
   int choice;
   char ans = 'N';
   int key;
   node *new_node, *root, *tmp, *parent;
   node *get_node();
   root = NULL;
   clrscr();

   printf("\nProgram For Binary Search Tree ");
   do {
      printf("\n1.Create");
      printf("\n2.Search");
      printf("\n3.Recursive Traversals");
      printf("\n4.Exit");
      printf("\nEnter your choice :");
      scanf("%d", &choice);

      switch (choice) {
      case 1:
         do {
            new_node = get_node();
            printf("\nEnter The Element ");
            scanf("%d", &new_node->data);

            if (root == NULL) /* Tree is not Created */
               root = new_node;
            else
               insert(root, new_node);

            printf("\nWant To enter More Elements?(y/n)");
            ans = getch();
         } while (ans == 'y');
         break;

      case 2:
         printf("\nEnter Element to be searched :");
         scanf("%d", &key);

         tmp = search(root, key, &parent);
         printf("\nParent of node %d is %d", tmp->data, parent->data);
         break;

      case 3:
         if (root == NULL)
            printf("Tree Is Not Created");
         else {
            printf("\nThe Inorder display : ");
            inorder(root);
            printf("\nThe Preorder display : ");
            preorder(root);
            printf("\nThe Postorder display : ");
            postorder(root);
         }
         break;
      }
   } while (choice != 4);
}
/*
 Get new Node
 */
node *get_node() {
   node *temp;
   temp = (node *) malloc(sizeof(node));
   temp->lchild = NULL;
   temp->rchild = NULL;
   return temp;
}
/*
 This function is for creating a binary search tree
 */
void insert(node *root, node *new_node) {
   if (new_node->data < root->data) {
      if (root->lchild == NULL)
         root->lchild = new_node;
      else
         insert(root->lchild, new_node);
   }

   if (new_node->data > root->data) {
      if (root->rchild == NULL)
         root->rchild = new_node;
      else
         insert(root->rchild, new_node);
   }
}
/*
 This function is for searching the node from
 binary Search Tree
 */
node *search(node *root, int key, node **parent) {
   node *temp;
   temp = root;
   while (temp != NULL) {
      if (temp->data == key) {
         printf("\nThe %d Element is Present", temp->data);
         return temp;
      }
      *parent = temp;

      if (temp->data > key)
         temp = temp->lchild;
      else
         temp = temp->rchild;
   }
   return NULL;
}
/*
 This function displays the tree in inorder fashion
 */
void inorder(node *temp) {
   if (temp != NULL) {
      inorder(temp->lchild);
      printf("%d", temp->data);
      inorder(temp->rchild);
   }
}
/*
 This function displays the tree in preorder fashion
 */
void preorder(node *temp) {
   if (temp != NULL) {
      printf("%d", temp->data);
      preorder(temp->lchild);
      preorder(temp->rchild);
   }
}

/*
 This function displays the tree in postorder fashion
 */
void postorder(node *temp) {
   if (temp != NULL) {
      postorder(temp->lchild);
      postorder(temp->rchild);
      printf("%d", temp->data);
   }
}

/* Binary Search Tree Insert,Search,Display(Preorder,Inorder,Postorder) */

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

typedef struct link
{
struct link *left;
int data;
struct link *right;
}node;

node *tree=NULL;
node *insert(node*,int);
void search(node *,int);
void preorder(node *);
void postorder(node *);
void inorder(node *);

int main()
{
int val,choice;
while(1)
{
printf("\n1: Insert\n2: Search\n3: Preorder\n4: Inorder\n5: Postorder\n6: Exit :\n");
puts("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:puts("Enter number : ");
 scanf("%d",&val);
 tree=insert(tree,val);
 break;
case 2:puts("Enter the number to be search : ");
  scanf("%d",&val);
  search(tree,val);
  break;
case 3:puts("\nPreorder traversing tree \n");
      preorder(tree);
      break;
case 4:puts("\nInoreder traversing tree \n");
      inorder(tree);
      break;
case 5:puts("\nPostorder traversing tree \n");
      postorder(tree);
      break;
case 6:puts("\nEnd");
  //exit(0);
}
}

getch();
return 0;
}

node *insert(node *tree,int val)
{
if(tree==NULL)
{
tree=(node *)malloc(sizeof(node));
tree->data=val;
tree->left=tree->right=NULL;
}
else if(val>tree->data)
tree->right=insert(tree->right,val);
else if(val<tree->data)
tree->left=insert(tree->left,val);
else
printf("\nDuplicate value: program exited ");
// exit(0);
return tree;
}

void search(node *tree,int v)
{
if(tree==NULL)
{
printf("\nSearch Unsuccessfull");
return;
}
else if(v==tree->data)
{
printf("\nSearch successfull\n Number =%d",v);
return;
}
else if(v<tree->data)
{
search(tree->left,v);
}
else
{
search(tree->right,v);
}
}

void inorder(node *tree)
{
if(tree!=NULL)
{
inorder(tree->left);
printf("%5d",tree->data);
inorder(tree->right);
}
}

void preorder(node *tree)
{
if(tree!=NULL)
{
printf("%5d",tree->data);
preorder(tree->left);
preorder(tree->right);
}
}

void postorder(node *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
printf("%5d",tree->data);
}
}

program for stack using linked list...........

#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *link;
}*start;

void push(int x);
void pop();
void display();

int main()
{

  int a, dt;
   start = NULL;
   while(1)
     {
      printf("\n 1 for push");
      printf("\n 2 for pop");
      printf("\n 3 for display");
      printf("\n 4 for exit");
      printf("\n Enter your choice");
      scanf("%d",&a);
      switch(a)
      {
      case 1: printf("\n Enter element to satck");
             scanf("%d",&dt);
             push(dt);
             break;
           
          case 2: pop();    
                 break;
               
          case 3: display();
       break;

//case 4: exit(0);
 
      }
     
     }

return 0;
}

void push(int d)
{
struct node *data, *tmp;

data = (struct node*)malloc(sizeof(struct node));

data->info = d;

data->link = NULL;
 
    if(start == NULL)
    start = data;
    else if(start->link == NULL)
    start->link = data;
    else
          {
             data->link = start;
             start = data;
         }
       
     
     
}

void pop()
{
struct node  *tmp;
if(start== NULL)
printf("stack is empty.....");
else
{
      tmp = start;
     start= tmp->link;
     free(tmp);
 }
}

void display()
{
struct node  *tmp=start;
if(start== NULL)
printf("stack is empty.....");
else
{  
     
 while(tmp != NULL)
    {
     printf("%3d",tmp->info);
     tmp=tmp->link;
}


}
}

program for queue using array......

#include<stdio.h>
#include<conio.h>

# define MAX 3
int stack[MAX];
void push(int x);
int rare = -1;
int front = -1;
void pop();
void display();

int main()
{
  int a, dt;
 
   while(1)
     {
      printf("\n 1 for push");
      printf("\n 2 for pop");
      printf("\n 3 for display");
      printf("\n 4 for exit");
      printf("\n Enter your choice");
      scanf("%d",&a);
      switch(a)
      {
      case 1: if(rare >= MAX)
                      printf("\n Queue is 8973982 full");
             else
             {
           
       printf("\n Enter element to Queue");
             scanf("%d",&dt);
             push(dt);
         }
             break;
           
          case 2: pop();
                 break;
               
          case 3: display();
       break;

//case 4: exit(0);
 
      }
     
     }

return 0;
}

void push(int data)
{
if(front == -1)
front = 0;

if(rare == MAX - 1)
printf("\n Queue is full");
else
{

rare++;
stack[rare] = data;
    }

}
void pop()
{
if(front>rare )
{
printf("\n queue is empty, deletion is not possible");


}
else
{

int tmp = stack[front];
front++;
printf("\nDeleted element of Queue is %d",tmp);    
}

}
void display()
{
int i;
printf("\n  elements of satck are.....\n");
for(i= front;i<=rare;i++)
printf(" %3d",stack[i]);
}

program for queue using linked list..........

#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *link;
}*start;


void insert(int);
void delt();
void display();

int main()
{

  int a, dt;
   start = NULL;
   while(1)
     {
      printf("\n 1 for insert");
      printf("\n 2 for delt");
      printf("\n 3 for display");
      printf("\n 4 for exit");
      printf("\n Enter your choice");
      scanf("%d",&a);
      switch(a)
      {
      case 1: printf("\n Enter element to satck");
             scanf("%d",&dt);
             insert(dt);
             break;
           
          case 2: delt();    
                 break;
               
          case 3: display();
       break;

//case 4: exit(0);
 
      }
     
     }

return 0;
}

void insert(int d)
{
   struct node *x , *y;
 
   x =  (struct node*)malloc(sizeof(struct node));
 
   x->info = d;
   x->link = NULL;
   if(start == NULL)
   start = x;
   else
   {
 
      y = start;
      while(y->link!= NULL)
      {
      y = y->link;
      }
      y->link= x;
}
}
 
void delt()
{
struct node  *y;

if(start == NULL)
printf("\n Queue is empty,Deletion is not possible\n");
else
  {
 
  y= start;
  printf("\n deleted element is\t %d ",y->info);
  start = y->link;
  free(y);
      }
}  
 
void display()  
{
    struct node  *y;

if(start == NULL)
{

printf("\n Queue is empty,Deletion is not possible\n");
}
else
{
y= start;
printf("\n Element of Queue are..........\n");
while(y!=NULL)
{
printf("\t %d",y->info);
y= y->link;
}
    }
 }
 
 
   

// program for singly linked list..........


#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *link;
}*start;


void create(int);
void insertAtBeg(int );
void insertAtMid(int , int );
void insertAtEnd(int );

void count();
void search(int);
void sort();
void delt(int);
void display();

int main()
{

  int a, dt,pos;
   start = NULL;
   while(1)
     {
      printf("\n 1 for create a node");
      printf("\n 2 for insert an item at begning");
      printf("\n 3 for insert a node at specific position");
      printf("\n 4 for insert a node at end");
      printf("\n 5 for sorting  ");
      printf("\n 6 for count how many nodes in list ");
      printf("\n 7 for search an item");
      printf("\n 8 for Deleting the item");
      printf("\n 9 for displaying all item of list");
     
     
     
      printf("\n Enter your choice \t");
      scanf("%d",&a);
      switch(a)
      {
      case 1: printf("\n Enter element to a node");
             scanf("%d",&dt);
             create(dt);
             break;
           
          case 2: printf("\n Enter element to a node");
             scanf("%d",&dt);
             insertAtBeg(dt);
             break;
           
               
          case 3:
       printf("\n Enter element to a node and their position");
             scanf("%d%d",&dt,&pos);
             insertAtMid(dt,pos);
             break;
           

case 4:         printf("\n Enter element to a node");
             scanf("%d",&dt);
             insertAtEnd(dt);
             break;
     
case 5:   sort();
        break;
       
        case 6:  count();
               break;
       
          case 7:         printf("\n Enter element to be search");
             scanf("%d",&dt);
             search(dt);
             break;
        case 8:          printf("\n Enter element to be deleted");
             scanf("%d",&dt);
             delt(dt);
             break;
           
         case 9: display();
                 break;
       

      }
     
     }

return 0;
}

void create(int d)
{
   struct node *x , *y , *z;
 
   x =  (struct node*)malloc(sizeof(struct node));
 
   x->info = d;
   x->link = NULL;
   if(start == NULL)
   start = x;
   else
   {
 
      y = start;
      while(y->link!= NULL)
      {
      y = y->link;
      }
      y->link= x;
  }
     
}
 
void delt(int d)
{
int dt;
struct node  *y,*x,*z;

if(start == NULL)
printf("\n List is empty,Deletion is not possible\n");
else
  {
 
  y= start;
  if(y->info== d)
  {
     dt == d;
  y = start;
  start = y->link;
  free(y);
  }
  else
  {
  y= start;
   z = start;
    while(y->link->link!=NULL)
   {
    if(y->link->info==d)
    {
    dt == d;
    x= y->link;
    y->link = x->link;
    free(x);
    return ;
    }
 
    y= y->link;
 
      }
      if(y->link->info == d)
      { dt = d;
     
      z=y->link ;
     y->link = NULL;
 
      free(z);
     
     
      }

 
  }
  if (d== dt)
   printf("\n deleted element is -  %d\t",d);
   else
    printf("\n  element is not found..,,,\t");
 
 
      }
}  
 
void display()  
{
    struct node  *y;

if(start == NULL)
{

printf("\n List is empty\n");
}
else
{
y= start;
printf("\n Element of List are..........\n");
while(y!=NULL)
{
printf("\t %d",y->info);
y= y->link;
}
}
 }
 
 
   void insertAtBeg(int d)
{
   struct node *x ;
 
   x =  (struct node*)malloc(sizeof(struct node));
 
   x->info = d;
   x->link = NULL;
   if(start == NULL)
 
   start = x;
   else
   {
 
    x->link = start;
    start = x;
  }
     
}

  void insertAtMid(int d,int p)
{
int i;
   struct node *x ,*y;
 
   x =  (struct node*)malloc(sizeof(struct node));
 
   x->info = d;
   x->link = NULL;
   if(start == NULL)
 
   start = x;
   else
   { y= start;
   for(i=1; i<p-1;i++)
    y=y->link ;
   
x->link = y->link;
y->link = x;
  }
     
}

  void insertAtEnd(int d)
{
   struct node *x ,*y;
 
   x =  (struct node*)malloc(sizeof(struct node));
 
   x->info = d;
   x->link = NULL;
   if(start == NULL)
 
   start = x;
   else
   {
     y = start;
     while(y->link!=NULL)
     y=y->link;
   
     y->link = x;
  }
     
}

void sort()
{
struct node *x,*y,*z;
int t;

if(start == NULL)
printf("\n list is empty\n");
else
{
y= start;
x= y->link;
for(;y!= NULL;y=y->link)
{
 for(;x!=NULL;x=x->link)
  {
    if(y->info > x->info)
    {
    t= x->info;
    x->info = y->info;
   
    y->info = t;
    printf("\t %d",y->info);
    }
  }
  printf("\n");
   }
z= start;
printf("\n sorted elements of list are....\n");  
while(z!=NULL)  
{
printf("\t %d",z->info);
z= z->link;
}
}
}

void search(int d)
{
int f=0,c=1;
struct node *p;
if(start == NULL)
printf("\n list is empty\n");
else
{
p=start;
while(p!=NULL)
{
if(p->info == d)
{
f=1;
break;
}
p=p->link;
c++;

}
if(f==1)
printf("\n %d found at %d pos....",d,c);
else
printf("\n %d is not found....",d,c);
}
}

void count()
{
int c=0;
struct node  *y;

if(start == NULL)
{

printf("\n List is empty\n");
}
else
{
y= start;

while(y!=NULL)
{

y= y->link;
c++;
}
printf("\n no of Element in List is ....\t %d",c);
}
}

output-----