C program for Binary Search Tree

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

struct searchtree
{
 int element;
 struct searchtree *left,*right;
}*root;
typedef struct searchtree *node;
typedef int ElementType;

node insert(ElementType, node);
node delet(ElementType, node);
void makeempty();
node findmin(node);
node findmax(node);
node find(ElementType, node);
void display(node, int);

void main()
{
 int ch;
 ElementType a;
 node temp;
 makeempty();
 while(1)
 {
  printf("\n1. Insert\n2. Delete\n3. Find\n4. Find min\n5. Find Max\n6. Display\n7. Exit\nEnter Your Choice : ");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1:
    printf("Enter an element : ");
    scanf("%d", &a);
    root = insert(a, root);
    break;
   case 2:
    printf("\nEnter the element to delete : ");
    scanf("%d",&a);
    root = delet(a, root);
    break;
   case 3:
    printf("\nEnter the element to search : ");
    scanf("%d",&a);
    temp = find(a, root);
    if (temp != NULL)
     printf("Element found");
    else
     printf("Element not found");
    break;
   case 4:
    temp = findmin(root);
    if(temp==NULL)
     printf("\nEmpty tree");
    else
     printf("\nMinimum element : %d", temp->element);
    break;
   case 5:
    temp = findmax(root);
    if(temp==NULL)
     printf("\nEmpty tree");
    else
     printf("\nMaximum element : %d", temp->element);
    break;
   case 6:
    if(root==NULL)
     printf("\nEmpty tree");
    else
     display(root, 1);
    break;
   case 7:
    exit(0);
   default:
    printf("Invalid Choice");
  }
 }
}

node insert(ElementType x,node t)
{
 if(t==NULL)
 {
  t = (node)malloc(sizeof(node));
  t->element = x;
  t->left = t->right = NULL;
 }
 else
 {
  if(x < t->element)
   t->left = insert(x, t->left);
  else if(x > t->element)
   t->right = insert(x, t->right);
 }
 return t;
}

node delet(ElementType x,node t)
{
 node temp;
 if(t == NULL)
  printf("\nElement not found");
 else
 {
  if(x < t->element)
   t->left = delet(x, t->left);
  else if(x > t->element)
   t->right = delet(x, t->right);
  else
  {
   if(t->left && t->right)
   {
    temp = findmin(t->right);
    t->element = temp->element;
    t->right = delet(t->element,t->right);
   }
   else if(t->left == NULL)
    t=t->right;
   else
    t=t->left;
  }
 }
 return t;
}
void makeempty()
{
 root = NULL;
}

node findmin(node temp)
{
 if(temp == NULL || temp->left == NULL)
  return temp;
 return findmin(temp->left);
}

node findmax(node temp)
{
 if(temp==NULL || temp->right==NULL)
  return temp;
 return findmax(temp->right);
}

node find(ElementType x, node t)
{
 if(t==NULL) return NULL;
 if(x<t->element) return find(x,t->left);
 if(x>t->element) return find(x,t->right);
 return t;
}

void display(node t,int level)
{
 int i;
 if(t)
 {
  display(t->right, level+1);
  printf(ā€œ\nā€);
  for(i=0;i<level;i++)
   printf(" ");
  printf("%d", t->element);
  display(t->left, level+1);
 }
}

Sample Output:

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 10

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 20

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 5

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 4
The smallest Number is 5

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 3
Enter an element : 100
Element not Found

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 2
Enter an element : 20

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 6
20
10

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 7

C program for Binary Search Tree Traversal

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

struct TreeNode;
typedef struct TreeNode *node;
typedef int ElementType;

struct TreeNode
{
 int element;
 node left, right;
}*root;

node insert(ElementType x,node t)
{
 if(t==NULL)
 {
  t = malloc(sizeof(node));
  t->element = x;
  t->left = t->right = NULL;
 }
 else
 {
  if(x < t->element)
   t->left = insert(x, t->left);
  else if(x > t->element)
   t->right = insert(x, t->right);
 }
 return t;
}

void printpreorder(node T)
{
 if(T != NULL)
 {
  printf("%d ", T->element);
  printpreorder(T->left);
  printpreorder(T->right);
 }
}

void printinorder(node T)
{
 if(T != NULL)
 {
  printinorder(T->left);
  printf("%d ", T->element);
  printinorder(T->right);
 }
}

void printpostorder(node T)
{
 if(T != NULL)
 {
  printpostorder(T->left);
  printpostorder(T->right);
  printf("%d ", T->element);
 }
}

void main()
{
 int ch;
 ElementType a;
 root = NULL;
 while(1)
 {
  clrscr();
  printf("\n1. Insert\n2. Print Pre Order\n3. Print In Order\n4. Print Post Order\n5. Exit\nEnter Your Choice : ");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1:
    printf("Enter an element : ");
    scanf("%d", &a);
    root = insert(a, root);
    break;
   case 2:
    printpreorder(root);
    break;
   case 3:
    printinorder(root);
    break;
   case 4:
    printpostorder(root);
    break;
   case 5:
    exit(0);
   default:
    printf("Invalid Choice");
  }
  getch();
 }
}

Sample Output:

1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 1
Enter an Element : 1

1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 1
Enter an Element : 5

1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 1
Enter an Element : 2

1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 1
Enter an Element : 7

1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 2
1 2 5 7

1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 3
1 5 2 7

1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 4
2 7 5 1

1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 5