PROGRAM 1(a)

Objective: Write a program in C for the implementation of Linear Search.

INTRODUCTION: A linear search is a basic and simple search algorithm. It searches

for an element or value in an array sequentially until the desired element is found. The
algorithm compares the target element with each element in the list, and if a match is
found, it returns the index of that element; otherwise, it returns -1. Linear search is
suitable for unsorted or unordered lists when there are relatively few elements.

// Linear Search in C

#include <stdio.h>

int search(int array[], int n, int x) {

// Going through array sequencially

for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}

int main() {
int array[] = {2, 4, 0, 1, 9};
int x = 1;
int n = sizeof(array) / sizeof(array[0]);

int result = search(array, n, x);

(result == -1) ? printf("Element not found") : printf("Element found at index: %d", result);
}
PROGRAM 1(b)
Objective: Write a program in C for the implementation of Binary Search.

INTRODUCTION: Binary search is applied to sorted arrays or lists. In binary search,

we first compare the value with the elements in the middle position of the array. If the
value matches, we return the value. If the value is less than the middle element, it must lie
in the lower half of the array; if it is greater, it must lie in the upper half. We repeat this
procedure on the relevant half of the array. Binary search is useful when dealing with
large numbers of elements.

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {

int low = 0, high = size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
 low = mid + 1;
else
high = mid - 1;
}
return -1;
}

int main() {
int arr[] = {10, 20, 30, 40, 50};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 40;
int result = binarySearch(arr, size, target);
if (result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found\n");
return 0;
}

PROGRAM 2(a)
Objective: Write a C Program to implement Bubble Sorting.

INTRODUCTION:

Bubble sort is a simple sorting algorithm. This sorting algorithm is a comparison-based

algorithm in which each pair of adjacent elements is compared, and the elements are
swapped if they are not in order. This algorithm is not suitable for large datasets as its
average and worst- case complexity is O(n2)O(n^2)O(n2), where nnn is the number of
items.

// Bubble sort in C

#include <stdio.h>

// perform the bubble sort

void bubbleSort(int array[], int size) {

// loop to access each array element

for (int step = 0; step < size - 1; ++step) {

// loop to compare array elements

for (int i = 0; i < size - step - 1; ++i) {

// compare two adjacent elements

 // change > to < to sort in descending order
if (array[i] > array[i + 1]) {

// swapping occurs if elements

// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}

// print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}

int main() {
int data[] = {-2, 45, 0, 11, -9};

// find the array's length

int size = sizeof(data) / sizeof(data[0]);

bubbleSort(data, size);

printf("Sorted Array in Ascending Order:\n");

printArray(data, size);
}
PROGRAM 2(b)
Objective: Write a C Program to implement Selection Sorting.

INTRODUCTION:

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place

comparison- based algorithm in which the list is divided into two parts: the sorted part at
the left end and the unsorted part at the right end. Initially, the sorted part is empty, and the
unsorted part is the entire list. The smallest element is selected from the unsorted array and
swapped with the leftmost element, making that element part of the sorted array. This
process continues, moving the unsorted array boundary by one element to the right. This
algorithm is not suitable for large datasets as its average and worst-case complexities are
O(n2)O(n^2)O(n2), where nnn is the number of items.

// C program for implementation of selection sort

#include <stdio.h>

void selectionSort(int arr[], int N) {

// Start with the whole array as unsored and one by

// one move boundary of unsorted subarray towards right
for (int i = 0; i < N - 1; i++) {

// Find the minimum element in unsorted array

int min_idx = i;
for (int j = i + 1; j < N; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}

// Swap the found minimum element with the first

// element in the unsorted part
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int N = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: \n");
for (int i = 0; i < N; i++) {
printf("%d ", arr[i]);
}
printf("\n");
 // Calling selection sort
selectionSort(arr, N);

printf("Sorted array: \n");

for (int i = 0; i < N; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
PROGRAM 2(c)
Objective: Write a C Program to implement Insertion Sorting.

INTRODUCTION:

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained,

which is always sorted. For example, the lower part of an array is maintained to be
sorted. An element that is to be 'inserted' in this sorted sub-list has to find its appropriate
place and then be inserted there, hence the name, Insertion Sort. The array is searched
sequentially, and unsorted items are moved and inserted into the sorted sub-list (in the
same array). This algorithm is not suitable for large datasets as its average and worst-
case complexity is O(n2)O(n^2)O(n2), where nnn is the number of items.

// C program to implement insertion sort

#include <math.h>
#include <stdio.h>

void insertionSort(int arr[], int N) {

// Starting from the second element

for (int i = 1; i < N; i++) {
int key = arr[i];
int j = i - 1;

// Move elements of arr[0..i-1], that are

// greater than key, to one position to
// the right of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
 }

// Move the key to its correct position

arr[j + 1] = key;
}
}

int main() {
int arr[] = { 12, 11, 13, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted array: ");

for (int i = 0; i < N; i++) {
printf("%d ", arr[i]);
}
printf("\n");

// Calling insertion sort on array arr

insertionSort(arr, N);

printf("Sorted array: ");

for (int i = 0; i < N; i++) {
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}
PROGRAM 2(d)
Objective: Write a Program in C for the implementation of Merge Sort.

// C program for the implementation of merge sort

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

// Merges two subarrays of arr[].

// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;

// Create temporary arrays

int leftArr[n1], rightArr[n2];

// Copy data to temporary arrays

for (i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];

// Merge the temporary arrays back into arr[left..right]

i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
}
else {
arr[k] = rightArr[j];
j++;
}
k++;
}

// Copy the remaining elements of leftArr[], if any

while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}

// Copy the remaining elements of rightArr[], if any

while (j < n2) {
arr[k] = rightArr[j];
 j++;
k++;
}
}

// The subarray to be sorted is in the index range [left-right]

void mergeSort(int arr[], int left, int right) {
if (left < right) {

// Calculate the midpoint

int mid = left + (right - left) / 2;

// Sort first and second halves

mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);

// Merge the sorted halves

merge(arr, left, mid, right);
}
}

int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);

// Sorting arr using mergesort

mergeSort(arr, 0, n - 1);

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

printf("%d ", arr[i]);
return 0;
}

PROGRAM 2(e)
Objective: Write a Program in C for the implementation of Heap Sort.

// C Program for HeapSort

#include <stdio.h>
// Heapify function
void heapify(int arr[], int n, int i)
{
int temp, maximum, left_index, right_index;

// currently assuming i postion to

// be holding the largest value
maximum = i;

// right child index

right_index = 2 * i + 2;

// left child index

left_index = 2 * i + 1;

// if left index value is grater than the current index

// value
if (left_index < n && arr[left_index] > arr[maximum])
maximum = left_index;

// if right index value is grater than the current index

// value
if (right_index < n && arr[right_index] > arr[maximum])
maximum = right_index;

// checking if we needed swaping the elements or not

if (maximum != i) {
temp = arr[i];
arr[i] = arr[maximum];
arr[maximum] = temp;
heapify(arr, n, maximum);
}
}

// HeapSorting function
void heapsort(int arr[], int n)
{
int i, temp;
 // performing heapify on the non leaf nodes so n/2 - 1
// to 0 are the non leaf nodes
for (i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// the current array is changed to max heap

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

temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}

// Driver code
int main()
{
// initializing the array
int arr[] = { 20, 18, 5, 15, 3, 2 };
int n = 6;

// Displaying original array

printf("Original Array : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

printf("\n");
heapsort(arr, n);

// Displaying sorted array

printf("Array after performing heap sort: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
 PROGRAM 3(a)

Objective: Write a program in C for the implementation of Stack Using Array (PUSH, POP
& Traversing).

INTRODUCTION: The C program is written for the implementation of a stack using an

array. The basic operations of a stack are PUSH(), POP(), and DISPLAY(). The PUSH
function in the code is used to insert an element at the top of the stack, while the POP
function is used to remove the element from the top of the stack. Finally, the DISPLAY
function is used to print the values at any time. All stack functions are implemented in C
code.

Algorithm:

#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
 pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}

}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");

}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
 {
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}
}

PROGRAM 3(b)

Objective: Write a program in C for the implementation of Stack Using Linked List
(PUSH, POP & Traversing).

Algorithm:

1. // C program to implement a stack using linked list

2. #include <stdio.h>
3. #include <stdlib.h>
4.
5. // ________LINKED LIST UTILITY FUNCITON____________
6.
7. // Define the structure for a node of the linked list
8. typedef struct Node {
9. int data;
10. struct Node* next;
11. } node;
12.
13. // linked list utility function
14. node* createNode(int data)
15. {
16. // allocating memory
17. node* newNode = (node*)malloc(sizeof(node));
18.
19. // if memory allocation is failed
20. if (newNode == NULL)
21. return NULL;
22.
23. // putting data in the node
24. newNode->data = data;
25. newNode->next = NULL;
26. return newNode;
27. }
28.
29. // fuction to insert data before the head node
30. int insertBeforeHead(node** head, int data)
31. {
32. // creating new node
33. node* newNode = createNode(data);
34. // if malloc fail, return error code
35. if (!newNode)
36. return -1;
37.
38. // if the linked list is empty
39. if (*head == NULL) {
40. *head = newNode;
41. return 0;
42. }
43.
44. newNode->next = *head;
45. *head = newNode;
46. return 0;
47. }
48.
49. // deleting head node
50. int deleteHead(node** head)
51. {
52. // no need to check for empty stack as it is already
53. // being checked in the caller function
54. node* temp = *head;
55. *head = (*head)->next;
56. free(temp);
57. return 0;
58. }
59.
60. // _________STACK IMPLEMENTATION STARTS HERE_________
61.
62. // Function to check if the stack is empty or not
63. int isEmpty(node** stack) { return *stack == NULL; }
64.
65. // Function to push elements to the stack
66. void push(node** stack, int data)
67. {
68. // inserting the data at the beginning of the linked
69. // list stack
70. // if the insertion function returns the non - zero
71. // value, it is the case of stack overflow
72. if (insertBeforeHead(stack, data)) {
73. printf("Stack Overflow!\n");
74. }
75. }
76.
77. // Function to pop an element from the stack
78. int pop(node** stack)
79. {
80. // checking underflow condition
81. if (isEmpty(stack)) {
82. printf("Stack Underflow\n");
83. return -1;
84. }
85.
86. // deleting the head.
87. deleteHead(stack);
88. }
89.
90. // Function to return the topmost element of the stack
91. int peek(node** stack)
92. {
93. // check for empty stack
94. if (!isEmpty(stack))
95. return (*stack)->data;
96. else
97. return -1;
98. }
99.
100. // Function to print the Stack
101. void printStack(node** stack)
102. {
103. node* temp = *stack;
104. while (temp != NULL) {
105. printf("%d-> ", temp->data);
106. temp = temp->next;
107. }
108. printf("\n");
109. }
110.
 111. // driver code
112. int main()
113. {
114. // Initialize a new stack top pointer
115. node* stack = NULL;
116.
117. // Push elements into the stack
118. push(&stack, 10);
119. push(&stack, 20);
120. push(&stack, 30);
121. push(&stack, 40);
122. push(&stack, 50);
123.
124. // Print the stack
125. printf("Stack: ");
126. printStack(&stack);
127. // Pop elements from the stack
128. pop(&stack);
129. pop(&stack);
130. // Print the stack after deletion of elements
131. printf("\nStack: ");
132. printStack(&stack);
133.
134. return 0;
135. }rn.

PROGRAM 4

Objective: Write a program in C to implement various operations on a linked list,

including adding elements to the beginning, middle, or end.

INTRODUCTION: A linked list is a linear data structure where each element is a

separate object. Each element (referred to as a node) of a list comprises two items: the
data and a reference to the next node. The last node has a reference to null. The entry
point into a linked list is called the head of the list. It should be noted that the head is not
a separate node, but a reference to the first node. If the list is empty, then the head is a
null reference. A linked list is a dynamic data structure; the number of nodes in a list is
not fixed and can grow and shrink on demand. Any application that has to deal with an
unknown number of objects will benefit from using a linked list.

// // C Program for Implementation of Singly Linked List

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

// Define the Node structure

struct Node {
 int data;
struct Node* next;
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to insert a new element at the beginning of the singly linked list
void insertAtFirst(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}

// Function to insert a new element at the end of the singly linked list
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

// Function to insert a new element at a specific position in the singly linked list
void insertAtPosition(struct Node** head, int data, int position) {
struct Node* newNode = createNode(data);
if (position == 0) {
insertAtFirst(head,data);
return;
 }
struct Node* temp = *head;
for (int i = 0; temp != NULL && i < position - 1; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("Position out of range\n");
free(newNode);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}

// Function to delete the first node of the singly linked list

void deleteFromFirst(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
*head = temp->next;
free(temp);
}

// Function to delete the last node of the singly linked list

void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}
while (temp->next->next != NULL) {
temp = temp->next;
 }
free(temp->next);
temp->next = NULL;
}

// Function to delete a node at a specific position in the singly linked list

void deleteAtPosition(struct Node** head, int position) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
if (position == 0) {
deleteFromFirst(head);
return;
}
for (int i = 0; temp != NULL && i < position - 1; i++) {
temp = temp->next;
}
if (temp == NULL || temp->next == NULL) {
printf("Position out of range\n");
return;
}
struct Node* next = temp->next->next;
free(temp->next);
temp->next = next;
}

// Function to print the LinkedList

void print(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

// Driver Code
int main() {
struct Node* head = NULL;

insertAtFirst(&head, 10);
printf("Linked list after inserting the node:10 at the beginning \n");
print(head);

printf("Linked list after inserting the node:20 at the end \n");

insertAtEnd(&head, 20);
print(head);

printf("Linked list after inserting the node:5 at the end \n");

insertAtEnd(&head, 5);
print(head);

printf("Linked list after inserting the node:30 at the end \n");

insertAtEnd(&head, 30);
print(head);

printf("Linked list after inserting the node:15 at position 2 \n");

insertAtPosition(&head, 15, 2);
print(head);

printf("Linked list after deleting the first node: \n");

deleteFromFirst(&head);
print(head);

printf("Linked list after deleting the last node: \n");

deleteFromEnd(&head);
print(head);

printf("Linked list after deleting the node at position 1: \n");

deleteAtPosition(&head, 1);
print(head);

return 0;
}

PROGRAM 5
Objective: Write a program in C for the implementation of simple Queue Using Array.

INTRODUCTION: A queue is an abstract data type or a linear data structure in which

the first element is inserted from one end called REAR (also called tail), and the deletion
of an existing element takes place from the other end called FRONT (also called head).
This makes the queue a FIFO (First In First Out) data structure, which means that the
element inserted first will also be removed first. The process to add an element into the
queue is called Enqueue, and the process of removal from the queue is called Dequeue.

// C Program to implement queue using arrays

#include <stdio.h>
// Define the maximum size for the queue
#define MAX_SIZE 100

// Define a structure for the queue

struct Queue {
int queue[MAX_SIZE];
int front;
int rear;
};

// Function to initialize the queue

void initializeQueue(struct Queue *q) {
q->front = -1;
q->rear = -1;
}

// Function to check if the queue is empty

int isEmpty(struct Queue *q) {
return (q->front == -1);
}

// Function to check if the queue is full

int isFull(struct Queue *q) {
return (q->rear == MAX_SIZE - 1);
}

// Function to insert an element into the queue

void enqueue(struct Queue *q, int data) {
if (isFull(q)) {
printf("Queue is full\n");
return;
}
if (isEmpty(q)) {
q->front = 0;
}
q->rear++;
q->queue[q->rear] = data;
printf("Enqueued %d in queue\n", data);
}

// Function to remove an element from the queue

int dequeue(struct Queue *q) {
if (isEmpty(q)) {
 printf("Queue is empty\n");
return -1;
}
int data = q->queue[q->front];
// If the queue is empty reset the pointers
if (q->front == q->rear) {
q->front = -1;
q->rear = -1;
} else {
q->front++;
}
printf("Deleted element: %d\n", data);
return data;
}

// Function to display the elements of the queue

void display(struct Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return;
}
for (int i = q->front; i <= q->rear; i++) {
printf("%d ", q->queue[i]);
}
printf("\n");
}

int main() {
// Initialize a queue
struct Queue q;
initializeQueue(&q);

enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
printf("Elements in the queue after enqueue operation: ");
display(&q);

dequeue(&q);
printf("Elements in the queue after dequeue operation: ");
display(&q);

return 0;
}

PROGRAM 6
AIM: Write a Program in C for the implementation of Insertion and Deletion in a BST
Using Linked List.

INTRODUCTION:

A Binary Search Tree (BST) is a node-based binary tree data structure that has the following
properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees. There
must be no duplicate nodes.

// C program to implement binary search tree

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

// Define a structure for a binary tree node

struct BinaryTreeNode {
int key;
struct BinaryTreeNode *left, *right;
};

// Function to create a new node with a given value

struct BinaryTreeNode* newNodeCreate(int value)
{
struct BinaryTreeNode* temp
= (struct BinaryTreeNode*)malloc(
sizeof(struct BinaryTreeNode));
temp->key = value;
temp->left = temp->right = NULL;
return temp;
}

// Function to search for a node with a specific key in the

// tree
struct BinaryTreeNode*
searchNode(struct BinaryTreeNode* root, int target)
{
if (root == NULL || root->key == target) {
return root;
}
if (root->key < target) {
return searchNode(root->right, target);
}
return searchNode(root->left, target);
}
// Function to insert a node with a specific value in the
// tree
struct BinaryTreeNode*
insertNode(struct BinaryTreeNode* node, int value)
{
if (node == NULL) {
return newNodeCreate(value);
}
if (value < node->key) {
node->left = insertNode(node->left, value);
}
else if (value > node->key) {
node->right = insertNode(node->right, value);
}
return node;
}

// Function to perform post-order traversal

void postOrder(struct BinaryTreeNode* root)
{
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf(" %d ", root->key);
}
}

// Function to perform in-order traversal

void inOrder(struct BinaryTreeNode* root)
{
if (root != NULL) {
inOrder(root->left);
printf(" %d ", root->key);
inOrder(root->right);
}
}

// Function to perform pre-order traversal

void preOrder(struct BinaryTreeNode* root)
{
if (root != NULL) {
printf(" %d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}

// Function to find the minimum value

struct BinaryTreeNode* findMin(struct BinaryTreeNode* root)
{
if (root == NULL) {
return NULL;
}
else if (root->left != NULL) {
return findMin(root->left);
}
return root;
}

// Function to delete a node from the tree

struct BinaryTreeNode* delete (struct BinaryTreeNode* root,
int x)
{
if (root == NULL)
return NULL;

if (x > root->key) {
root->right = delete (root->right, x);
}
else if (x < root->key) {
root->left = delete (root->left, x);
}
else {
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
 else if (root->left == NULL
|| root->right == NULL) {
struct BinaryTreeNode* temp;
if (root->left == NULL) {
temp = root->right;
}
else {
temp = root->left;
}
free(root);
return temp;
}
else {
struct BinaryTreeNode* temp
= findMin(root->right);
root->key = temp->key;
root->right = delete (root->right, temp->key);
}
}
return root;
}

int main()
{
// Initialize the root node
struct BinaryTreeNode* root = NULL;

// Insert nodes into the binary search tree

root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);

// Search for a node with key 60

if (searchNode(root, 60) != NULL) {
printf("60 found");
 }
else {
printf("60 not found");
}

printf("\n");

// Perform post-order traversal

postOrder(root);
printf("\n");

// Perform pre-order traversal

preOrder(root);
printf("\n");

// Perform in-order traversal

inOrder(root);
printf("\n");

// Perform delete the node (70)

struct BinaryTreeNode* temp = delete (root, 70);
printf("After Delete: \n");
inOrder(root);

// Free allocated memory (not done in this code, but

// good practice in real applications)

return 0;
}

PROGRAM 7
AIM: To implement binary tree, binary search tree, and tree traversal using a linked list.

INTRODUCTION:

Binary Search on Singly Linked List Approach:

Here, the start node (set to head of the list) and the last node (set to NULL initially) are
given.
• Middle is calculated using a two-pointers approach.
• If the middle’s data matches the required value of the search, return it.
• Else if middle’s data < value, move to the upper half (setting start to middle's next).
 • Else go to the lower half (setting last to middle).
• The condition to exit is either element found or the entire list is traversed.
When the entire list is traversed, last points to start (i.e., last->next == start).
// C program to implement binary search tree
#include <stdio.h>
#include <stdlib.h>

// Define a structure for a binary tree node

struct BinaryTreeNode {
int key;
struct BinaryTreeNode *left, *right;
};

// Function to create a new node with a given value

struct BinaryTreeNode* newNodeCreate(int value)
{
struct BinaryTreeNode* temp
= (struct BinaryTreeNode*)malloc(
sizeof(struct BinaryTreeNode));
temp->key = value;
temp->left = temp->right = NULL;
return temp;
}

// Function to search for a node with a specific key in the

// tree
struct BinaryTreeNode*
searchNode(struct BinaryTreeNode* root, int target)
{
if (root == NULL || root->key == target) {
return root;
}
if (root->key < target) {
return searchNode(root->right, target);
}
return searchNode(root->left, target);
}

// Function to insert a node with a specific value in the

// tree
struct BinaryTreeNode*
insertNode(struct BinaryTreeNode* node, int value)
{
if (node == NULL) {
return newNodeCreate(value);
}
if (value < node->key) {
node->left = insertNode(node->left, value);
}
else if (value > node->key) {
node->right = insertNode(node->right, value);
}
return node;
}

// Function to perform post-order traversal

void postOrder(struct BinaryTreeNode* root)
{
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf(" %d ", root->key);
}
}

// Function to perform in-order traversal

void inOrder(struct BinaryTreeNode* root)
{
if (root != NULL) {
inOrder(root->left);
printf(" %d ", root->key);
inOrder(root->right);
}
}

// Function to perform pre-order traversal

void preOrder(struct BinaryTreeNode* root)
{
if (root != NULL) {
 printf(" %d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}

// Function to find the minimum value

struct BinaryTreeNode* findMin(struct BinaryTreeNode* root)
{
if (root == NULL) {
return NULL;
}
else if (root->left != NULL) {
return findMin(root->left);
}
return root;
}

// Function to delete a node from the tree

struct BinaryTreeNode* delete (struct BinaryTreeNode* root,
int x)
{
if (root == NULL)
return NULL;

if (x > root->key) {
root->right = delete (root->right, x);
}
else if (x < root->key) {
root->left = delete (root->left, x);
}
else {
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
else if (root->left == NULL
|| root->right == NULL) {
struct BinaryTreeNode* temp;
 if (root->left == NULL) {
temp = root->right;
}
else {
temp = root->left;
}
free(root);
return temp;
}
else {
struct BinaryTreeNode* temp
= findMin(root->right);
root->key = temp->key;
root->right = delete (root->right, temp->key);
}
}
return root;
}

int main()
{
// Initialize the root node
struct BinaryTreeNode* root = NULL;

// Insert nodes into the binary search tree

root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);

// Search for a node with key 60

if (searchNode(root, 60) != NULL) {
printf("60 found");
}
else {
printf("60 not found");
 }

printf("\n");

// Perform post-order traversal

postOrder(root);
printf("\n");

// Perform pre-order traversal

preOrder(root);
printf("\n");

// Perform in-order traversal

inOrder(root);
printf("\n");

// Perform delete the node (70)

struct BinaryTreeNode* temp = delete (root, 70);
printf("After Delete: \n");
inOrder(root);

// Free allocated memory (not done in this code, but

// good practice in real applications)

return 0;
}

PROGRAM 8

PART 1

Objective: Write a program in C to implement depth-first search.

Introduction: DFS traversal of a graph produces a spanning tree as the final result. A
spanning tree is a graph without loops. We use a stack data structure with a maximum
size equal to the total number of vertices in the graph to implement DFS traversal.
#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

// Structure for a node in the adjacency list

struct Node {

int data;

struct Node* next;

};

// Structure for the adjacency list

struct List {

struct Node* head;

};

// Structure for the graph

struct Graph {

int vertices;

struct List* array;

};

// Function to create a new node

struct Node* createNode(int data) {

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

 newNode->data = data;

newNode->next = NULL;

return newNode;

// Function to create a graph with a given number of vertices

struct Graph* createGraph(int vertices) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

graph->vertices = vertices;

graph->array = (struct List*)malloc(vertices * sizeof(struct List));

for (int i = 0; i < vertices; i++) {

graph->array[i].head = NULL;

return graph;

// Function to add an edge to the graph

void addEdge(struct Graph* graph, int src, int dest) {

struct Node* newNode = createNode(dest);

newNode->next = graph->array[src].head;

graph->array[src].head = newNode;
 // Uncomment the following code to make the graph undirected

/*

newNode = createNode(src);

newNode->next = graph->array[dest].head;

graph->array[dest].head = newNode;

*/

// Function to perform Depth First Search (DFS) from a given vertex

void DFS(struct Graph* graph, int vertex, bool visited[]) {

visited[vertex] = true;

printf("%d ", vertex);

struct Node* currentNode = graph->array[vertex].head;

while (currentNode) {

int adjacentVertex = currentNode->data;

if (!visited[adjacentVertex]) {

DFS(graph, adjacentVertex, visited);

currentNode = currentNode->next;

// Function to perform DFS traversal from a given vertex in a specified order

void DFSTraversal(struct Graph* graph, int* order, int orderSize) {

bool* visited = (bool*)malloc(graph->vertices * sizeof(bool));

for (int i = 0; i < graph->vertices; i++) {

visited[i] = false;

for (int i = 0; i < orderSize; i++) {

if (!visited[order[i]]) {

DFS(graph, order[i], visited);

free(visited);

int main() {

int vertices = 4;

struct Graph* graph = createGraph(vertices);

addEdge(graph, 2, 0);

addEdge(graph, 0, 2);

addEdge(graph, 1, 2);

addEdge(graph, 0, 1);

addEdge(graph, 3, 3);
 addEdge(graph, 1, 3);

int order[] = {2, 0, 1, 3};

int orderSize = sizeof(order) / sizeof(order[0]);

printf("Following is Depth First Traversal (starting from vertex 2):\n");

DFSTraversal(graph, order, orderSize);

return 0;

PART 2

Objective: Write a program in C to implement breadth-first search.

Introduction: BFS traversal of a graph produces a spanning tree as the final result. A
spanning tree is a graph without loops. We use a queue data structure with a maximum
size equal to the total number of vertices in the graph to implement BFS traversal.

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

#define MAX_VERTICES 50

// This struct represents a directed graph using

// adjacency list representation
typedef struct Graph_t {

// No. of vertices
int V;
bool adj[MAX_VERTICES][MAX_VERTICES];
} Graph;

// Constructor
Graph* Graph_create(int V)
{
Graph* g = malloc(sizeof(Graph));
 g->V = V;

for (int i = 0; i < V; i++) {

for (int j = 0; j < V; j++) {
g->adj[i][j] = false;
}
}

return g;
}

// Destructor
void Graph_destroy(Graph* g) { free(g); }

// Function to add an edge to graph

void Graph_addEdge(Graph* g, int v, int w)
{
// Add w to v’s list.
g->adj[v][w] = true;
}

// Prints BFS traversal from a given source s

void Graph_BFS(Graph* g, int s)
{
// Mark all the vertices as not visited
bool visited[MAX_VERTICES];
for (int i = 0; i < g->V; i++) {
visited[i] = false;
}

// Create a queue for BFS

int queue[MAX_VERTICES];
int front = 0, rear = 0;

// Mark the current node as visited and enqueue it

visited[s] = true;
queue[rear++] = s;

while (front != rear) {

// Dequeue a vertex from queue and print it

s = queue[front++];
printf("%d ", s);

// Get all adjacent vertices of the dequeued

// vertex s.
// If an adjacent has not been visited,
// then mark it visited and enqueue it
for (int adjacent = 0; adjacent < g->V;
adjacent++) {
 if (g->adj[s][adjacent] && !visited[adjacent]) {
visited[adjacent] = true;
queue[rear++] = adjacent;
}
}
}
}

// Driver code
int main()
{
// Create a graph
Graph* g = Graph_create(4);
Graph_addEdge(g, 0, 1);
Graph_addEdge(g, 0, 2);
Graph_addEdge(g, 1, 2);
Graph_addEdge(g, 2, 0);
Graph_addEdge(g, 2, 3);
Graph_addEdge(g, 3, 3);

printf("Following is Breadth First Traversal "

"(starting from vertex 2) \n");
Graph_BFS(g, 2);
Graph_destroy(g);

return 0;
}