1.

Write a C program that uses functions to perform the following on Singly Linked List: i)
Creation ii) Insertion iii) Deletion iv) Traversal

Source Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*head,*newn,*trav,*temp;
void create_list()
{
int value;
temp=head;
newn=(struct node *)malloc(sizeof (struct node));
printf("\nenter the value to be inserted");
scanf("%d",&value);
newn->data=value;
if(head==NULL)
{
head=newn;
head->next=NULL;
}
else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newn;
newn->next=NULL;
}
}
void insert_at_begning(int value)
{
newn=(struct node*)malloc(sizeof(struct node));
newn->data=value;
if(head==NULL)
{
head=newn;
head->next=NULL;
}
else
{
newn->next=head;
head=newn;
}
}
void insert_at_end(int value)
{
temp=head;
newn=(struct node *)malloc(sizeof (struct node));
newn->data=value;
if(head==NULL)
{
head=newn;
head->next=NULL;
}
else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newn;
newn->next=NULL;
}
}
void insert_at_middle()
{
int loc,value;
printf("\n after which value you want to insert : ");
scanf("%d",&loc);
printf("\nenter the value to be inserted");
scanf("%d",&value);
newn=(struct node*)malloc(sizeof(struct node));
newn->data=value;
temp=head;
if(head==NULL)
{
head=newn;
head->next=NULL;
}
else
{
while(temp->data!=loc)
{
temp=temp->next;
}
newn->next=temp->next;
temp->next=newn;
}
}
void delete_from_middle()
{
struct node *var;
int value;
temp=head;
printf("\nenter the data that you want to delete from the list shown above");
scanf("%d",&value);
if(temp==NULL)
{
printf("\nSORRY...there is no %d element",value);
}
else
{
while(temp->data!=value)
{
var=temp;
temp=temp->next;
}
var->next=temp->next;
temp->next=NULL;
free(temp);
}
}
void delete_from_front()
{
temp=head;
if(head==NULL)
{
printf("\nno elements for deletion in the list\n");
}
else
{
head=temp->next;
temp->next=NULL;
free(temp);
}
}
void delete_from_end()
{
struct node *var;
temp=head;
if(head==NULL)
{
printf("\nno elemts in the list");
}
else
{
while(temp->next!=NULL)
{
var=temp;
temp=temp->next;
}
var->next=NULL;
free(temp);
}
}
void display()
{
temp=head;
if(temp==NULL)
{
printf("\nList is Empty\n");
}
else
{
while(temp!=NULL)
{
printf(" -> %d ",temp->data);
temp=temp->next;
}
printf("\n");
}
}
void main()
{
int ch=0;
char ch1;
head=NULL;
printf("\[Link] linked list");
printf("\[Link] at begning of linked list");
printf("\[Link] at the end of linked list");
printf("\[Link] at the middle where you want");
printf("\[Link] from the front of linked list");
printf("\[Link] from the end of linked list ");
printf("\[Link] of the middle data that you want");
printf("\[Link] the linked list");
printf("\[Link]\n");
while(1)
{
printf("\nenter the choice of operation to perform on linked list");
scanf("%d",&ch);
switch(ch)
{
case 1:
{
do{
create_list();
display();
printf("do you want to create list ,y / n");
getchar();
scanf("%c",&ch1);
}while(ch1=='y'||ch1=='Y');
break;
}
case 2:
{
int value;
printf("\nenter the value to be inserted");
scanf("%d",&value);
insert_at_begning(value);
display();
break;
}
case 3:
{
int value;
printf("\nenter value to be inserted");
scanf("%d",&value);
insert_at_end(value);
display();
break;
}
case 4:
{
insert_at_middle();
display();
break;
}
case 5:
{
delete_from_front();
display();
break;
}
case 6:
{
delete_from_end();
display();
break;
}
case 7:
{
display();
delete_from_middle();
display();
break;
}
case 8:
{
display();
break;
}
case 9:
{
exit(1);
}
default:printf("\n****Please enter correct choice****\n");
}
getch();
}
}
Output :
2. Write a program that uses functions to perform the following operations on doubly
linked list.: i) Creation ii) Insertion iii) Deletion iv) Traversal
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next,*prev;
}*head,*newn,*trav,*temp;
void create_list()
{
int value;
temp=head;
newn=(struct node*)malloc(sizeof(struct node));
printf("\n enter value");
scanf("%d",&value);
newn->data=value;
if(head==NULL)
{
head=newn;
newn->prev=NULL;
newn->next=NULL;
}
else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
newn->next=NULL;
newn->prev=temp;
temp->next=newn;
temp=newn;
}
}
void insert_at_begning(int value)
{
newn=(struct node*)malloc(sizeof(struct node));
newn->data=value;
if(head==NULL)
{
head=newn;
head->prev=NULL;
head->next=NULL;
}
else
{
newn->next=head;
head->prev=newn;
newn->prev=NULL;
head=newn;
}
}
void insert_at_end(int value)
{
temp=head;
newn=(struct node*)malloc(sizeof(struct node));
newn->data=value;
if(head==NULL)
{
head=newn;
head->prev=NULL;
head->next=NULL;
}
else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
newn->next=NULL;
newn->prev=temp;
temp->next=newn;
temp=newn;
}
}
void insert_at_middle()
{
struct node *var;
int loc,value;
printf("\nselect location where you want to insert the data");
scanf("%d",&loc);
printf("\nenter which value do u want to inserted");
scanf("%d",&value);
newn=(struct node*)malloc(sizeof(struct node));
newn->data=value;
temp=head;
if(temp==NULL)
{
printf("\n the list is empty");
}
else
{
while(temp->data!=loc)
{
temp=temp->next;
var=temp->next;
}
temp->next=newn;
newn->prev=temp;
newn->next=var;
var->prev=newn;
}
}
void delete_from_middle()
{
int loc;
struct node *var;
temp=head;
printf("\nenter the data that you want to delete from the list shown above");
scanf("%d",&loc);
if(head==NULL)
{
printf("The list is empty\n");
}
else
{
while(temp->data!=loc)
{
var=temp;
temp=temp->next;
}
var->next=temp->next;
temp->next->prev=var;
temp->prev=NULL;
temp->next=NULL;
free(temp);
}
}
void delete_from_front()
{
struct node *var;
temp=head;
if(head==NULL)
{
printf("no elements for deletion in the list");
}
else
{
var=temp->next;
head=temp->next;
temp->next=NULL;
temp->prev=NULL;
var->prev=NULL;
free(temp);
}
}
void delete_from_end()
{
struct node *var;
temp=head;
if(head==NULL)
{
printf("no elemts in the list");
}
else
{
while(temp->next!=NULL)
{
var=temp;
temp=temp->next;
}
var->next=NULL;
temp->prev=NULL;
free(temp);
}
}
void display()
{
trav=head;
if(trav==NULL)
{
printf("\nList is Empty");
}
else
{
while(trav!=NULL)
{
printf("%d<--> ",trav->data);
trav=trav->next;
}
printf("\n");
}
}
void main()
{
int ch=0;
char ch1;
clrscr();
head=NULL;
printf("\n Double Linked List Operations");
printf("\[Link] Double Linked List");
printf("\[Link] at begning of linked list");
printf("\[Link] at the end of linked list");
printf("\[Link] at the middle where you want");
printf("\[Link] from the front of linked list");
printf("\[Link] from the end of linked list ");
printf("\[Link] of the middle data that you want");
printf("\[Link]");
printf("\[Link]\n");
while(1)
{
printf("\nenter the choice of operation to perform on linked list");
scanf("%d",&ch);
switch(ch)
{
case 1:
{
do{
create_list();
display();
printf("do you want to create list ,y / n");
getchar();
scanf("%c",&ch1);
}while(ch1=='y'||ch1=='Y');
break;
}
case 2:
{
int value;
printf("\nenter the value to be inserted");
scanf("%d",&value);
insert_at_begning(value);
display();
break;
}
case 3:
{
int value;
printf("\nenter value to be inserted");
scanf("%d",&value);
insert_at_end(value);
display();
break;
}
case 4:
{
insert_at_middle();
display();
break;
}
case 5:
{
delete_from_front();
display();
break;
}
case 6:
{
delete_from_end();
display();
break;
}
case 7:
{
display();
delete_from_middle();
display();
break;
}
case 8:
{
display();
break;
}
case 9:
{
exit(0);
}
}
}
getch();
}
Output :
3. Write a program that uses functions to perform the following operations on circular
linked list.: i) Creation ii) Insertion iii) Deletion iv) Traversal
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head=NULL;
void beginsert ();
void lastinsert ();
void insertatspecified();
void begin_delete();
void last_delete();
void delete_from_middle();
void display();
void main ()
{
int choice =0;
clrscr();
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\[Link] in begining\[Link] at last\n [Link] at specified location \n [Link] from
Beginning\n [Link] from last\n6.random_delete\[Link]\[Link]\n");
while(1)
{
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
display();
break;
case 2:
lastinsert();
display();
break;
case 3:
insertatspecified();
display();
break;
case 4:
begin_delete();
display();
break;
case 5:
last_delete();
display();
break;
case 6:
delete_from_middle();
display();
break;
case 7:
display();
break;
case 8:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *newn,*temp;
int value;
temp = head;
newn = (struct node *)malloc(sizeof(struct node));
printf("\nEnter the node data?");
scanf("%d",&value);
newn -> data = value;
if(head == NULL)
{
head = newn;
newn -> next = head;
}
else
{
while(temp->next != head)
{
temp = temp->next;
}
newn->next = head;
temp -> next = newn;
head = newn;
}
printf("\nnode inserted\n");
}
void lastinsert()
{
struct node *newn,*temp;
int value;
temp=head;
newn = (struct node *)malloc(sizeof(struct node));
printf("\nEnter Data?");
scanf("%d",&value);
newn->data = value;
if(head == NULL)
{
head = newn;
newn -> next = head;
}
else
{
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = newn;
newn -> next = head;
temp=newn;
}
printf("\nnode inserted\n");
}
void insertatspecified()
{
struct node *newn,*temp,*var;
int value,loc;
temp=head;
newn = (struct node *)malloc(sizeof(struct node));
printf("enter the specified location value");
scanf("%d",&loc);
printf("\nEnter Data?");
scanf("%d",&value);
newn->data = value;
if(head == NULL)
{
head = newn;
newn -> next = head;
}
else
{
while(temp->data!=loc)
{
var=temp;
temp=temp->next;
}
newn->next=var->next;
var->next=newn;
}
printf("node inserted");
}
void begin_delete()
{
struct node *temp,*var;
temp=var=head;
if(temp == NULL)
{
printf("\nLinked list is empty");
}
else
{
while(var->next != head)
{
var=var->next;
}
head=temp->next;
temp->next=NULL;
var->next=head;
printf("\nnode deleted\n");
}
}

void last_delete()
{
struct node *temp,*var;
temp=head;
if(temp==NULL)
{
printf("\nUNDERFLOW");
}
else
{
while(temp->next!=head)
{
var=temp;
temp=temp->next;
}
var->next = temp -> next;
temp->next=NULL;
free(temp);
printf("\nnode deleted\n");
}
}
void delete_from_middle()
{
struct node *temp,*var;
int value;
temp=head;
printf("\nenter the data that you want to delete from the list shown above");
scanf("%d",&value);
if(temp==NULL)
{
printf("\nSORRY...there is no %d element",value);
}
else
{
while(temp->data!=value)
{
var=temp;
temp=temp->next;
}
var->next=temp->next;
temp->next=NULL;
}
printf("\ndata deleted from list is %d",value);
free(temp);
}
void display()
{
struct node *trav;
trav=head;
if(head == NULL)
{
printf("\nnothing to print");
}
else
{
printf("\n printing values ... \n");
while(trav -> next != head)
{
printf("%d\n", trav -> data);
trav = trav -> next;
}
printf("%d\n", trav -> data);
}
}
Output :
4. i)Write a program that implement stack (its operations) using Arrays
#define MAX 4 //you can take any number to limit your stack size
#include<stdio.h>
#include<conio.h>

int stack[MAX];
int top;

void push()
{
char a;
int value;
if(top==MAX-1)
{
printf("Stack full or stack overflow");
return;
}
do
{
 printf("\n Enter the value to be inserted:");
scanf("%d",&value);
top=top+1;
stack[top]=value;
printf("do you want to continue insertion Y/N");
getchar();
scanf("%c",&a);
}while(a=='y'||a=='Y');
}

void pop()
{
int t;
if(top==-1)
{
printf("Stack empty or stack overflow");
}
t=stack[top];
top=top-1;
printf("The deleted element id :%d",t);
}

void show()
{
int i;
printf("\nThe Stack elements are:");
for(i=top;i>=0;i--)
{
printf("%d",stack[i]);
}
}
void main()
{
char ch;
int choice,value;
top=-1;
clrscr();
printf("[Link]");
printf("\[Link]");
printf("\[Link] or display");
printf("\n [Link]");

do
{
printf("\nEnter your choice for the operation: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
show();
break;
}
case 2:
{
pop();
show();
break;
}
case 3:
 {
show();
break;
}
case 4:
{
exit(1);
}
default:printf("Wrong choice");
}
printf("\nDo you want to continue(y/n):");
getchar();
scanf("%c",&ch);
}
while(ch=='y'||ch=='Y');
getch();
}

Output:
ii) Write a program that implement stack (its operations) using Pointers
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*top;

void push(int value)

{
struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=value;
if(top==NULL)
{
top=temp;
top->next=NULL;
 }
else
{
temp->next=top;
top=temp;
}
}
void pop()
{
struct node *temp,*var=top;
if(top==NULL)
{
Printf(“The stack is empty\”):
}
else
{
top=top->next;
free(var);
}
}
void display()
{
struct node *var=top;
if(top==NULL)
{
Printf(“The stack is empty”);
}
Else
{
printf("\nElements are as:\n");
while(var!=NULL)
 {
printf("\t%d\n",var->data);
var=var->next;
}
printf("\n");
}
}
void main()
{
int i=0;
top=NULL;
clrscr();
printf(" \n1. Push to stack");
printf(" \n2. Pop from Stack");
printf(" \n3. Display data of Stack");
printf(" \n4. Exit\n");
while(1)
{
printf(" \nChoose Option: ");
scanf("%d",&i);
switch(i)
{
case 1:
{
int value;
printf("\nEnter a valueber to push into Stack: ");
scanf("%d",&value);
push(value);
display();
break;
}
 case 2:
{
pop();
display();
break;
}
case 3:
{
display();
break;
}
case 4:
{
exit(0);
}
default:
{
printf("\nwrong choice for operation");
}
}
}
}
Output :
5. i) Write a program that implement Queue (its operations) using Arrays
#include <stdio.h>
#define MAX 5
void insert();
void delete();
void display();
int queue[MAX];
int rear=-1;
int front=-1;
void main()
{
int choice;
clrscr();
printf("[Link] element to queue \n");
printf("[Link] element from queue \n");
printf("[Link] all elements of queue \n");
printf("[Link] \n");
while(1)
{
 printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
display();
break;
case 2:
delete();
display();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}
}
}

void insert()
{
int value;
if (rear==MAX-1)
{
printf("Queue Overflow \n");
}
 else
{
if (front == - 1)
{
front=front+1;
}
printf("Inset the element in queue : ");
scanf("%d", &value);
rear=rear+1;
queue[rear] =value;
}
}
void delete()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue[front]);
front = front + 1;
}
}

void display()
{
int i;
if (front == - 1)
printf("Queue is empty \n");
 else
{
printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue[i]);
printf("\n");
}
}

ii) Write a program that implement Queue (its operations) using Pointers
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
struct queue
{
int data;
struct queue *next;
}*front=NULL,*rear=NULL;
void add();
void del();
void display();
void main()
{
int ch;
clrscr();
printf("[Link] an element in Queue\n");
printf("[Link] an element from Queue\n");
printf("[Link] the Queue\n");
printf("[Link]\n");
while(1)
{
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:add();
display();
break;
case 2:del();
display();
break;
case 3:display();
getch();
break;
case 4:exit(0);
break;
default:printf("\nYou entered wrong choice");
}
}
getch();
}
void add()
{
struct queue *newn;
int value;
newn=(struct queue*)malloc(sizeof(struct queue));
printf("\nEnter the element:");
scanf("%d",&value);
newn->data=value;
newn->next=NULL;
if(front==NULL&&rear==NULL)
{
rear=front=newn;
}
else
{
rear->next=newn;
rear=newn;
}
}
void del()
{
struct queue *temp;
temp=front;
if(front==NULL)
{
printf("\nQueue is Empty");
}
else
{
printf("deleted data %d\n",front->data);
front=front->next;
free(temp);
}
}
void display()
{
struct queue *temp;
if(front==NULL)
{
printf("queue is empty");
}
else
{
temp=front;
while(temp!=NULL)
{
printf("->%d",temp->data);
temp=temp->next;
}
}
}
Output :
6. Write a program that implements the following sorting methods to sort a given list of Integers in

a ascending order

i) Quick sort :

#include<stdio.h>

#include<conio.h>

//quick Sort function to Sort Integer array list

void quicksort(int array[], int firstIndex, int lastIndex)

{
//declaaring index variables

int pivotIndex, temp, index1, index2;

if(firstIndex < lastIndex)

//assigninh first element index as pivot element

pivotIndex = firstIndex;

index1 = firstIndex;

index2 = lastIndex;

//Sorting in Ascending order with quick sort

while(index1 < index2)

while(array[index1] <= array[pivotIndex] && index1 < lastIndex)

index1++;

while(array[index2]>array[pivotIndex])

index2--;

if(index1<index2)

//Swapping opertation

temp = array[index1];

array[index1] = array[index2];

array[index2] = temp;

//At the end of first iteration, swap pivot element with index2 element

temp = array[pivotIndex];
 array[pivotIndex] = array[index2];

array[index2] = temp;

//Recursive call for quick sort, with partiontioning

quicksort(array, firstIndex, index2-1);

quicksort(array, index2+1, lastIndex);

void main()

//Declaring variables

int array[100],n,i;

//Number of elements in array form user input

printf("Enter the number of element you want to Sort : ");

scanf("%d",&n);

//code to ask to enter elements from user equal to n

printf("Enter Elements in the list : ");

for(i = 0; i < n; i++)

scanf("%d",&array[i]);

//calling quickSort function defined above

quicksort(array,0,n-1);

//print sorted array

printf("Sorted elements: ");

for(i=0;i<n;i++)

printf(" %d",array[i]);

getch();

Output :
ii) Heap sort:

#include <stdio.h>

void heapify(int arr[], int n, int i)

int temp,maximum,left_index,right_index;

maximum = i;

right_index=2*i+2;

left_index=2*i+1;

if(left_index<n&&arr[left_index]>arr[maximum])

maximum=left_index;

if(right_index<n&&arr[right_index]>arr[maximum])

maximum=right_index;

if(maximum!=i)

temp=arr[i];

arr[i]=arr[maximum];
 arr[maximum]=temp;

heapify(arr,n,maximum);

void heapsort(int arr[],int n)

int i,temp;

for (i=n/2-1;i>=0;i--)

heapify(arr,n,i);

for (i=n-1;i>0;i--)

temp=arr[0];

arr[0]=arr[i];

arr[i]=temp;

heapify(arr,i,0);

void main()

int arr[20],n,i;

clrscr();

printf("Enter the number of elements you want");

scanf("%d",&n);

printf("Enter the elements : ");

for(i=0;i<n;i++)

scanf("%d",&arr[i]);

}
 printf("\n");

heapsort(arr, n);

printf("Array after performing heap sort: ");

for(i=0;i<n;i++)

printf("%d\t", arr[i]);

getch();

Output:

III)Merge sort:

#include <stdio.h>

#define max 10

int a[10]={76,32,21,12,45,26,57,54,24,48};

int b[10];

void merging(int low,int mid,int high)

int l1,l2,i;

l1=low;
 l2=mid+1;

for(i=low;l1<=mid&&l2<=high;i++)

if(a[l1]<=a[l2])

b[i]=a[l1++];

else

b[i]=a[l2++];

while(l1<=mid)

b[i++]=a[l1++];

while(l2 <= high)

b[i++]=a[l2++];

for(i=low;i<=high;i++)

a[i]=b[i];

void sort(int low,int high)

int mid;

if(low<high)

mid=(low+high)/2;

sort(low,mid);

sort(mid+1,high);

merging(low,mid,high);

void main()

int i;

clrscr();
 printf("Enter the elements \n");

for(i=0;i<max;i++)

printf("%d\n",a[i]);

sort(0,max);

printf("\nList after sorting\n");

for(i=0;i<max;i++)

printf("%d\t",a[i]);

getch();

Output:

7. Write a program to implement the tree traversal methods (Recursive and Non Recursive) ?

#include <stdio.h>

#include <stdlib.h>

struct node {

int item;

struct node* left;

 struct node* right;

};

// Inorder traversal

void inorderTraversal(struct node* root) {

if (root == NULL) return;

inorderTraversal(root->left);

printf("%d ->", root->item);

inorderTraversal(root->right);

// preorderTraversal traversal

void preorderTraversal(struct node* root) {

if (root == NULL) return;

printf("%d ->", root->item);

preorderTraversal(root->left);

preorderTraversal(root->right);

// postorderTraversal traversal

void postorderTraversal(struct node* root) {

if (root == NULL) return;

postorderTraversal(root->left);

postorderTraversal(root->right);

printf("%d ->", root->item);

// Create a new Node

struct node* createNode(value) {

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

newNode->item = value;

newNode->left = NULL;

newNode->right = NULL;

return newNode;
}

// Insert on the left of the node

struct node* insertLeft(struct node* root, int value) {

root->left = createNode(value);

return root->left;

// Insert on the right of the node

struct node* insertRight(struct node* root, int value) {

root->right = createNode(value);

return root->right;

void main() {

struct node* root = createNode(1);

clrscr();

insertLeft(root, 12);

insertRight(root, 9);

insertLeft(root->left, 5);

insertRight(root->left, 6);

printf("Inorder traversal \n");

inorderTraversal(root);

printf("\nPreorder traversal \n");

preorderTraversal(root);

printf("\nPostorder traversal \n");

postorderTraversal(root);

getch();

Output:
8) Write a program to implement
i) Binary Search tree ii) B Trees iii) B+ Trees iv) AVL trees v) Red - Black trees

i) Binary Search tree :

#include <stdio.h>

#include <stdlib.h>

struct node

int data;

struct node *right_child;

struct node *left_child;

};

struct node* new_node(int x)

struct node *temp;

temp = malloc(sizeof(struct node));

temp->data = x;

temp->left_child=NULL;

temp->right_child=NULL;
 return temp;

struct node* search(struct node * root,int x)

if(root==NULL||root->data==x)

return root;

else if(x>root->data)

return search(root->right_child,x);

else

return search(root->left_child,x);

struct node* insert(struct node * root, int x){

if (root == NULL)

return new_node(x);

else if(x>root->data)

root->right_child=insert(root->right_child,x);

else

root->left_child=insert(root->left_child,x);

return root;

struct node* find_minimum(struct node * root) {

if (root == NULL)

return NULL;

else if(root->left_child!=NULL)

return find_minimum(root->left_child);

return root;

struct node* delete(struct node * root, int x)

{

if(root==NULL)

return NULL;

if(x>root->data)

root->right_child=delete(root->right_child, x);

else if(x<root->data)

root->left_child=delete(root->left_child,x);

else {

if(root->left_child==NULL&&root->right_child==NULL){

free(root);

return NULL;

else if(root->left_child==NULL||root->right_child==NULL){

struct node *temp;

if (root->left_child==NULL)

temp=root->right_child;

else

temp=root->left_child;

free(root);

return temp;

else {

struct node *temp=find_minimum(root->right_child);

root->data=temp->data;

root->right_child=delete(root->right_child,temp->data);

return root;

}
void inorder(struct node *root){

if (root!=NULL)

inorder(root->left_child);

printf(" %d ", root->data);

inorder(root->right_child);

void main()

struct node *root;

root=new_node(20);

clrscr();

insert(root,5);

insert(root,1);

insert(root,15);

insert(root,9);

insert(root,7);

insert(root,12);

insert(root,30);

insert(root,25);

insert(root,40);

insert(root,45);

insert(root,42);

search(root,7);

inorder(root);

printf("\n");
 root=delete(root,1);

root=delete(root,40);

root=delete(root,45);

root=delete(root,9);

inorder(root);

printf("\n");

getch();

Output :

ii) B Trees:
#include <stdio.h>

#include <stdlib.h>

#define MAX 3

#define MIN 2

struct btree_node

int data_item[MAX+1],counter;

struct btree_node *the_link[MAX+1];

};

struct btree_node *root_node;

struct btree_node *create_node(int data_item, struct btree_node *child_node) {

struct btree_node *new_node;

new_node=(struct btree_node*)malloc(sizeof(struct btree_node));

new_node->data_item[1]=data_item;

new_node->counter=1;

new_node->the_link[0]=root_node;

new_node->the_link[1]=child_node;

return new_node;

void insert_value(int data_item, int position, struct btree_node *the_node,

struct btree_node *child_node) {

int j=the_node->counter;

while(j>position) {

the_node->data_item[j+1]=the_node->data_item[j];

the_node->the_link[j+1]=the_node->the_link[j];

j--;

the_node->data_item[j+1]=data_item;

the_node->the_link[j+1]=child_node;

the_node->counter++;

void splitNode(int data_item, int *p_value, int position, struct btree_node *the_node,

struct btree_node *child_node, struct btree_node **new_node) {

int median_key,j;

if(position>MIN)

median_key=MIN+1;

else
median_key=MIN;

*new_node=(struct btree_node*)malloc(sizeof(struct btree_node));

j = median_key+1;

while(j<=MAX) {

(*new_node)->data_item[j-median_key]=the_node->data_item[j];

(*new_node)->the_link[j-median_key]=the_node->the_link[j];

j++;

the_node->counter=median_key;

(*new_node)->counter=MAX-median_key;

if(position<=MIN) {

insert_value(data_item,position,the_node,child_node);

} else {

insert_value(data_item,position-median_key,*new_node,child_node);

*p_value=the_node->data_item[the_node->counter];

(*new_node)->the_link[0]=the_node ->the_link[the_node->counter];

the_node -> counter--;

int set_node_value(int data_item, int *p_value,

struct btree_node *the_node, struct btree_node **child_node) {

int position;

if(!the_node) {

*p_value = data_item;

*child_node = NULL;

return 1;

if(data_item<the_node ->data_item[1]) {

position = 0;
 } else {

for(position = the_node -> counter;

(data_item<the_node ->data_item[position] && position > 1); position--);

if (data_item == the_node ->data_item[position]) {

printf("Duplicates are not allowed\n");

return 0;

if (set_node_value(data_item, p_value, the_node->the_link[position], child_node)) {

if (the_node->counter < MAX) {

insert_value(*p_value, position, the_node, *child_node);

} else {

splitNode(*p_value, p_value, position, the_node, *child_node, child_node);

return 1;

return 0;

void insertion_operation(int data_item) {

int the_flag, i;

struct btree_node *child_node;

the_flag = set_node_value(data_item, &i, root_node, &child_node);

if (the_flag)

root_node = create_node(i, child_node);

void copy_successor(struct btree_node *my_node, int position) {

struct btree_node *dummy_node;

dummy_node = my_node ->the_link[position];

for (; dummy_node ->the_link[0] != NULL;)

dummy_node = dummy_node ->the_link[0];

my_node ->data_item[position] = dummy_node ->data_item[1];

void right_shift(struct btree_node *my_node, int position) {

struct btree_node *x = my_node ->the_link[position];

int j = x -> counter;

while (j > 0) {

x ->data_item[j + 1] = x ->data_item[j];

x ->the_link[j + 1] = x ->the_link[j];

x ->data_item[1] = my_node->data_item[position];

x ->the_link[1] = x->the_link[0];

x -> counter++;

x = my_node ->the_link[position - 1];

my_node ->data_item[position] = x ->data_item[x -> counter];

my_node ->the_link[position] = x ->the_link[x -> counter];

x -> counter--;

return;

void left_shift(struct btree_node *my_node, int position) {

int j = 1;

struct btree_node *x = my_node ->the_link[position - 1];

x -> counter++;

x ->data_item[x -> counter] = my_node ->data_item[position];

x ->the_link[x -> counter] = my_node ->the_link[position] ->the_link[0];

x = my_node ->the_link[position];

my_node ->data_item[position] = x ->data_item[1];

x ->the_link[0] = x ->the_link[1];
 x -> counter--;

while (j <= x -> counter) {

x ->data_item[j] = x ->data_item[j + 1];

x ->the_link[j] = x ->the_link[j + 1];

j++;

return;

void merge_nodes(struct btree_node *my_node, int position) {

int j = 1;

struct btree_node *x1 = my_node ->the_link[position], *x2 = my_node ->the_link[position - 1];

x2 -> counter++;

x2 ->data_item[x2 -> counter] = my_node ->data_item[position];

x2 ->the_link[x2 -> counter] = my_node ->the_link[0];

while (j <= x1 -> counter) {

x2 -> counter++;

x2 ->data_item[x2 -> counter] = x1 ->data_item[j];

x2 ->the_link[x2 -> counter] = x1 ->the_link[j];

j++;

j = position;

while (j <my_node -> counter) {

my_node ->data_item[j] = my_node ->data_item[j + 1];

my_node ->the_link[j] = my_node ->the_link[j + 1];

j++;

my_node -> counter--;

free(x1);

}
void adjustNode(struct btree_node *my_node, int position) {

if (!position) {

if (my_node ->the_link[1] -> counter > MIN) {

left_shift(my_node, 1);

} else {

merge_nodes(my_node, 1);

} else {

if (my_node ->counter != position) {

if (my_node ->the_link[position - 1] -> counter > MIN) {

right_shift(my_node, position);

} else {

if (my_node ->the_link[position + 1] -> counter > MIN) {

left_shift(my_node, position + 1);

} else {

merge_nodes(my_node, position);

} else {

if (my_node ->the_link[position - 1] -> counter > MIN)

right_shift(my_node, position);

else

merge_nodes(my_node, position);

void tree_traversal(struct btree_node *my_node) {

int i;

if (my_node) {
 for (i = 0; i<my_node -> counter; i++) {

tree_traversal(my_node ->the_link[i]);

printf("%d ", my_node ->data_item[i + 1]);

tree_traversal(my_node ->the_link[i]);

void main() {

int data_item,ch;

clrscr();

insertion_operation(4);

insertion_operation(6);

insertion_operation(2);

insertion_operation(8);

insertion_operation(10);

insertion_operation(9);

insertion_operation(1);

insertion_operation(3);

insertion_operation(12);

insertion_operation(11);

insertion_operation(13);

printf("The B Tree is : ");

tree_traversal(root_node);

getch();

Output:
iii) B+ Trees:

iV) AVL trees:

v) Red Black tree:

9. Write a program to implement the graph traversal methods.

i)Depth first search:

#include<stdio.h>

#include<stdlib.h>

#define maxx 20

#define false 0

#define true 1

void create_graph();

void displayt();

void dfs(int v);

int adjt[maxx][maxx];

int visited[maxx];

int nt;

void main()

int i,v,choice;

system("cls");

create_graph();

printf("[Link] matrix\n");
printf("[Link] first search using stack \n");

printf("[Link] \n");

while(1)

printf("enter your choice:");

scanf("%d",&choice);

switch(choice)

case 1:

printf("\n Adjacency matrix \n");

displayt();

break;

case 2:

printf("\n enter starting node for depth first search:");

scanf("%d",&v);

for(i=1;i<=nt;i++)

visited[i]=false;

dfs(v);

break;

case 3:

return;

default:

printf("\n wrong choice \n");

break;

void create_graph()

{
int i,max_edges,source,destin;

char graph_type;

printf("\n enter number of nodes:");

scanf("%d",&nt);

printf("enter the type of matrix");

fflush(stdin);

scanf("%c",&graph_type);

max_edges=nt*(nt-1)/2;

for(i=1;i<=max_edges;i++)

printf("\n enter edges %d(00 to quit):",i);

scanf("%d%d",&source,&destin);

if((source==0)&&(destin==0))

break;

if(source>nt||destin>nt||source<=0||destin<=0)

printf("\n invalid edge!\n");

i--;

else

adjt[source][destin]=1;

if(graph_type=='u')

adjt[destin][source]=1;

void displayt()

{
int i,j;

for(i=1;i<=nt;i++)

for(j=1;j<=nt;j++)

printf("%4d",adjt[i][j]);

printf("\n");

void dfs(int v)

int i,stack[maxx],top=-1,pop_v,j,t;

top++;

stack[top]=v;

while(top>=0)

pop_v=stack[top];

top--;

if(visited[pop_v]==false)

printf("%d",pop_v);

visited[pop_v]=true;

else

continue;

for(i=nt;i>=1;i--)

if((adjt[pop_v][i]==1)||(visited[i]==false))

top++;
stack[top]=i;

Output:

ii)Breadth first search:

#include<stdio.h>

#include<stdlib.h>

#define Maxx 20

#define false 0

#define true 1

void create_grapht();

void displayt();

void bfs(int v);

void adj_nodes(int v);

int adj[Maxx][Maxx];

int visited[Maxx];

int nt;
void main()

int i,v,choice;

system("cls");

printf("\[Link] matrix\n");

printf("\[Link] first search\n");

printf("\[Link] vertices\n");

printf("[Link]\n");

while(1)

printf("\n enter your choice");

scanf("%d",&choice);

switch(choice)

case 1:

create_grapht();

printf("Adjacency matrix\n");

displayt();

break;

case 2:

printf("\n enter node for Breadth first search:");

scanf("%d",&v);

for(i=1;i<=nt;i++)

visited[i]=false;

bfs(v);

break;

case 3:

printf("\n enter node to final adjacent vertices:");

scanf("%d",&v);

printf("\n Adjacent vertices are:");

adj_nodes(v);

break;

case 4:

exit(0);

break;

default:

printf("\n wrong choice");

break;

//getch();

void create_grapht()

int i,max_edges,source,destin;

char graph_type;

printf("\n enter number of nodes:");

scanf("%d",&nt);

printf("enter type of graph D/u");

fflush(stdin);

scanf("%c",&graph_type);

max_edges=nt*(nt-1)/2;

for(i=1;i<=max_edges;i++)

printf("\n enter edge%d(00 to quit):",i);

scanf("%d%d",&source,&destin);

if((source==0)&&(destin==0))

break;

if(source>nt||destin>nt||source<=0||destin<=0)

{
printf("\n invalid edge\n");

i--;

else

adj[source][destin]=1;

if(graph_type=='u')

adj[destin][source]=1;

void displayt()

int i,j;

for(i=1;i<=nt;i++)

for(j=1;j<=nt;j++)

printf("%d\t",adj[i][j]);

printf("\n");

void bfs(int v)

int i,front,rear;

int que[20];

front=rear=-1;

printf("%d",v);

visited[v]=true;

rear++;

front++;
que[rear]=v;

while(front<=rear)

v=que[front];

front++;

for(i=1;i<=nt;i++)

if(adj[v][i]==1&&visited[i]==false)

printf("%d",i);

visited[i]=true;

rear++;

que[rear]=i;

void adj_nodes(int v)

int i;

for(i=1;i<=nt;i++)

if(adj[v][i]==1)

printf("%d",i);

printf("\n");

Output:
[Link] a pattern matching algorithms using Boyer-Moore, Knuh-Morris-Pratt.

i) Boyer-Moore :

#include <stdio.h>

#include <string.h>

#define ALPHABET_SIZE 256

// Function to compute the maximum of two integers

int max(int a, int b) {

return (a > b) ? a : b;
}

// Function to preprocess the pattern and generate the bad character heuristic table

void generateBadCharHeuristic(char *pattern, int patternLength, int badCharHeuristic[ALPHABET_SIZE])

int i;

for (i = 0; i< ALPHABET_SIZE; i++)

badCharHeuristic[i] = -1; // Initialize all entries to -1

for (i = 0; i<patternLength; i++)

badCharHeuristic[(int)pattern[i]] = i;

// Function to perform Boyer-Moore search

void searchBoyerMoore(char *text, char *pattern) {

int textLength = strlen(text);

int patternLength = strlen(pattern);

int badCharHeuristic[ALPHABET_SIZE];

int shift=0;

generateBadCharHeuristic(pattern, patternLength, badCharHeuristic);

// int shift = 0; // Initialize the shift to 0

while (shift <= textLength - patternLength) {

int j = patternLength - 1;

while (j >= 0 && pattern[j] == text[shift + j]) {

j--;

if (j < 0) {

// Pattern found at index 'shift'

printf("Pattern found at index %d\n", shift);

 // Move the window

shift += (shift + patternLength<textLength) ?patternLength - badCharHeuristic[(int)text[shift +

patternLength]] : 1;

} else {

// Shift the pattern according to bad character heuristic

shift += max(1, j - badCharHeuristic[(int)text[shift + j]]);

int main()

char text[] = "AABAACAADAABAABA";

char pattern[] = "AABA";

clrscr();

printf("Text: %s\n", text);

printf("Pattern: %s\n", pattern);

searchBoyerMoore(text, pattern);

return 0;

ii)Knuh-Morris-Pratt:
#include <stdio.h>

#include <string.h>

// Function to compute the LPS (Longest Prefix Suffix) array

void computeLPSArray(char *pattern, int patternLength, int *lps) {

int len = 0;

int i = 1;

lps[0] = 0;

while (i<patternLength) {

if (pattern[i] == pattern[len]) {

len++;

lps[i] = len;

i++;

} else {

if (len != 0) {

len = lps[len - 1];

} else {

lps[i] = 0;

i++;

// Function to perform KMP search

void searchKMP(char *text, char *pattern) {

int textLength = strlen(text);

int patternLength = strlen(pattern);

int *lps = (int *)malloc(sizeof(int) * patternLength);

int i=0,j=0;

computeLPSArray(pattern, patternLength, lps);

// int i = 0; // index for text[]

// int j = 0; // index for pattern[]

while (i<textLength) {

if (pattern[j] == text[i]) {

j++;

i++;

if (j == patternLength) {

// Pattern found at index 'i - j'

printf("Pattern found at index %d\n", i - j);

j = lps[j - 1];

} else if (i<textLength&& pattern[j] != text[i]) {

if (j != 0) {

j = lps[j - 1];

} else {

i++;

free(lps);

int main() {

char text[] = "AABAACAADAABAABA";

char pattern[] = "AABA";

clrscr();

printf("Text: %s\n", text);

printf("Pattern: %s\n", pattern);

searchKMP(text, pattern);

return 0;
}

Output: