1

1.

Write a program that uses functions to perform the following operations on singly linked

list.: i) Creation ii) Insertion iii) Deletion iv) Traversal

Aim

To perform operations on a singly linked list (Creation, Insertion, Deletion, Traversal) in C.

Program Logic

1. createList(): This function allows the user to create nodes for a linked list by inputting values until
-1 is entered, which stops node creation.

2. insertNode(): This function inserts a new node at a specified position in the list (0 for beginning).

3. deleteNode(): This function deletes a node at a specified position in the list (0 for beginning).

4. traverseList(): This function prints all elements in the linked list.

#include <stdio.h>

#include <stdlib.h>

// Node structure definition

struct Node {

int data;

struct Node* next;

};

// Global head pointer

struct Node* head = NULL;

// Function Prototypes

void createList();

void insertNode();

void deleteNode();
 2

void traverseList();

int main() {

int choice;

while (1) {

// Menu

printf("\nSingly Linked List Operations:\n");

printf("1. Create List\n2. Insert Node\n3. Delete Node\n4. Traverse List\n5. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

// Switch-case for operation selection

switch (choice) {

case 1: createList(); break;

case 2: insertNode(); break;

case 3: deleteNode(); break;

case 4: traverseList(); break;

case 5: printf("\nExiting Program.\n"); return 0;

default: printf("Invalid choice! Please try again.\n");

// Function Definitions

// i) Creation

void createList() {

int value;
 3

struct Node* newNode;

printf("Enter data for the new node (enter -1 to stop): ");

scanf("%d", &value);

while (value != -1) {

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

newNode->data = value;

newNode->next = NULL;

if (head == NULL) {

head = newNode;

} else {

struct Node* temp = head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;

printf("Enter data for the new node (enter -1 to stop): ");

scanf("%d", &value);

// ii) Insertion

void insertNode() {

int position, value;

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

 4

struct Node* temp = head;

printf("Enter the position to insert at (0 for beginning): ");

scanf("%d", &position);

printf("Enter data for the new node: ");

scanf("%d", &value);

newNode->data = value;

newNode->next = NULL;

if (position == 0) {

newNode->next = head;

head = newNode;

} else {

for (int i = 0; temp != NULL && i < position - 1; i++) {

temp = temp->next;

if (temp == NULL) {

printf("Position out of bounds.\n");

free(newNode);

} else {

newNode->next = temp->next;

temp->next = newNode;

// iii) Deletion
 5

void deleteNode() {

int position;

struct Node* temp = head;

printf("Enter the position to delete from (0 for beginning): ");

scanf("%d", &position);

if (position == 0) {

if (head != NULL) {

head = head->next;

free(temp);

} else {

printf("List is empty.\n");

} else {

struct Node* prev = NULL;

for (int i = 0; temp != NULL && i < position; i++) {

prev = temp;

temp = temp->next;

if (temp == NULL) {

printf("Position out of bounds.\n");

} else {

prev->next = temp->next;

free(temp);

}
 6

// iv) Traversal

void traverseList() {

struct Node* temp = head;

if (temp == NULL) {

printf("List is empty.\n");

} else {

printf("Linked List elements: ");

while (temp != NULL) {

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

temp = temp->next;

printf("NULL\n");

Output and Results

• Output:

o The program displays a menu with options to create, insert, delete, and traverse the linked
list.

o Upon selecting Create List, the user can input values for nodes until -1 is entered to stop.

o Insert Node allows inserting a new node at a specific position in the list.

o Delete Node removes a node from a specified position.

o Traverse List displays all nodes in the list.

• Results:

o The program successfully performs singly linked list operations as chosen by the user,
modifying and displaying the list accordingly.
 7

2. Write a program that uses functions to perform the following operations on doubly linked

list.: i) Creation ii) Insertion iii) Deletion iv) Traversal

Aim

To perform operations on a doubly linked list (Creation, Insertion, Deletion, Traversal) in C.

Program Logic

1. createList(): Allows the user to input values to create nodes in a doubly linked list until -1 is
entered, which stops node creation.

2. insertNode(): Inserts a new node at a specified position in the list (0 for beginning).

3. deleteNode(): Deletes a node at a specified position in the list (0 for beginning).

4. traverseList(): Prints all elements in the doubly linked list from head to tail.

#include <stdio.h>

#include <stdlib.h>

// Node structure definition

struct Node {

int data;

struct Node* prev;

struct Node* next;

};

// Global head pointer

struct Node* head = NULL;

// Function Prototypes

void createList();

void insertNode();

void deleteNode();
 8

void traverseList();

int main() {

int choice;

while (1) {

// Menu

printf("\nDoubly Linked List Operations:\n");

printf("1. Create List\n2. Insert Node\n3. Delete Node\n4. Traverse List\n5. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

// Switch-case for operation selection

switch (choice) {

case 1: createList(); break;

case 2: insertNode(); break;

case 3: deleteNode(); break;

case 4: traverseList(); break;

case 5: printf("\nExiting Program.\n"); return 0;

default: printf("Invalid choice! Please try again.\n");

// Function Definitions

// i) Creation

void createList() {

int value;
 9

struct Node* newNode, *temp;

printf("Enter data for the new node (enter -1 to stop): ");

scanf("%d", &value);

while (value != -1) {

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

newNode->data = value;

newNode->prev = newNode->next = NULL;

if (head == NULL) {

head = newNode;

} else {

temp = head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;

newNode->prev = temp;

printf("Enter data for the new node (enter -1 to stop): ");

scanf("%d", &value);

// ii) Insertion

void insertNode() {

int position, value;

 10

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

struct Node* temp = head;

printf("Enter the position to insert at (0 for beginning): ");

scanf("%d", &position);

printf("Enter data for the new node: ");

scanf("%d", &value);

newNode->data = value;

newNode->prev = newNode->next = NULL;

if (position == 0) {

if (head != NULL) {

newNode->next = head;

head->prev = newNode;

head = newNode;

} else {

for (int i = 0; temp != NULL && i < position - 1; i++) {

temp = temp->next;

if (temp == NULL) {

printf("Position out of bounds.\n");

free(newNode);

} else {

newNode->next = temp->next;

if (temp->next != NULL) {

temp->next->prev = newNode;
 11

temp->next = newNode;

newNode->prev = temp;

// iii) Deletion

void deleteNode() {

int position;

struct Node* temp = head;

printf("Enter the position to delete from (0 for beginning): ");

scanf("%d", &position);

if (position == 0) {

if (head != NULL) {

head = head->next;

if (head != NULL) {

head->prev = NULL;

free(temp);

} else {

printf("List is empty.\n");

} else {

for (int i = 0; temp != NULL && i < position; i++) {

temp = temp->next;

}
 12

if (temp == NULL) {

printf("Position out of bounds.\n");

} else {

if (temp->prev != NULL) {

temp->prev->next = temp->next;

if (temp->next != NULL) {

temp->next->prev = temp->prev;

free(temp);

// iv) Traversal

void traverseList() {

struct Node* temp = head;

if (temp == NULL) {

printf("List is empty.\n");

} else {

printf("Doubly Linked List elements: ");

while (temp != NULL) {

printf("%d <-> ", temp->data);

temp = temp->next;

printf("NULL\n");

}
 13

Output and Results

• Output:

o The program displays a menu with options to create, insert, delete, and traverse the
doubly linked list.

o Upon selecting Create List, the user can input values for nodes until -1 is entered to stop.

o Insert Node allows inserting a new node at a specific position in the list.

o Delete Node removes a node from a specified position.

o Traverse List displays all nodes in the list from head to tail.

• Results:

o The program successfully performs doubly linked list operations as chosen by the user,
modifying and displaying the list accordingly.

3. Write a program that uses functions to perform the following operations on circular linked

list.: i) Creation ii) Insertion iii) Deletion iv) Traversal

Aim

To perform operations on a circular linked list (Creation, Insertion, Deletion, Traversal) in C.

Program Logic

1. createList(): Allows the user to input values to create nodes in a circular linked list until -1 is
entered, which stops node creation.

2. insertNode(): Inserts a new node at a specified position in the list (0 for beginning).

3. deleteNode(): Deletes a node at a specified position in the list (0 for beginning).

4. traverseList(): Prints all elements in the circular linked list starting from the head and looping back
to it.

#include <stdio.h>

#include <stdlib.h>

// Node structure definition

struct Node {
 14

int data;

struct Node* next;

};

// Global head pointer

struct Node* head = NULL;

// Function Prototypes

void createList();

void insertNode();

void deleteNode();

void traverseList();

int main() {

int choice;

while (1) {

// Menu

printf("\nCircular Linked List Operations:\n");

printf("1. Create List\n2. Insert Node\n3. Delete Node\n4. Traverse List\n5. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

// Switch-case for operation selection

switch (choice) {

case 1: createList(); break;

case 2: insertNode(); break;

case 3: deleteNode(); break;

case 4: traverseList(); break;

 15

case 5: printf("\nExiting Program.\n"); return 0;

default: printf("Invalid choice! Please try again.\n");

// Function Definitions

// i) Creation

void createList() {

int value;

struct Node* newNode, *temp;

printf("Enter data for the new node (enter -1 to stop): ");

scanf("%d", &value);

while (value != -1) {

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

newNode->data = value;

newNode->next = newNode;

if (head == NULL) {

head = newNode;

newNode->next = head;

} else {

temp = head;

while (temp->next != head) {

temp = temp->next;

}
 16

temp->next = newNode;

newNode->next = head;

printf("Enter data for the new node (enter -1 to stop): ");

scanf("%d", &value);

// ii) Insertion

void insertNode() {

int position, value;

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

struct Node* temp = head;

printf("Enter the position to insert at (0 for beginning): ");

scanf("%d", &position);

printf("Enter data for the new node: ");

scanf("%d", &value);

newNode->data = value;

newNode->next = NULL;

if (position == 0) {

if (head == NULL) {

head = newNode;

newNode->next = head;

} else {

while (temp->next != head) {

 17

temp = temp->next;

newNode->next = head;

temp->next = newNode;

head = newNode;

} else {

for (int i = 0; temp->next != head && i < position - 1; i++) {

temp = temp->next;

newNode->next = temp->next;

temp->next = newNode;

// iii) Deletion

void deleteNode() {

int position;

struct Node *temp = head, *prev;

printf("Enter the position to delete from (0 for beginning): ");

scanf("%d", &position);

if (head == NULL) {

printf("List is empty.\n");

return;

}
 18

if (position == 0) {

if (head->next == head) {

free(head);

head = NULL;

} else {

while (temp->next != head) {

temp = temp->next;

temp->next = head->next;

free(head);

head = temp->next;

} else {

for (int i = 0; temp->next != head && i < position; i++) {

prev = temp;

temp = temp->next;

if (temp == head) {

printf("Position out of bounds.\n");

} else {

prev->next = temp->next;

free(temp);

// iv) Traversal

void traverseList() {
 19

struct Node* temp = head;

if (head == NULL) {

printf("List is empty.\n");

} else {

printf("Circular Linked List elements: ");

do {

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

temp = temp->next;

} while (temp != head);

printf("(back to head)\n");

Output and Results

• Output:

o The program displays a menu with options to create, insert, delete, and traverse the
circular linked list.

o Upon selecting Create List, the user can input values for nodes until -1 is entered to stop.

o Insert Node allows inserting a new node at a specific position in the list.

o Delete Node removes a node from a specified position.

o Traverse List displays all nodes in the list starting from head and looping back to head.

• Results:

o The program successfully performs circular linked list operations as chosen by the user,
modifying and displaying the list accordingly.

4. Write a program that implement stack (its operations) using

i) Arrays ii) Pointers

Program 1: Stack Using Arrays

 20

Aim

To implement stack operations (Push, Pop, Display) using arrays in C.

Program Logic

1. push(): Adds an element to the top of the stack if it's not full.

2. pop(): Removes the top element if the stack is not empty.

3. display(): Shows all elements in the stack from top to bottom.

#include <stdio.h>

#define MAX 5

// Array-based Stack

int stack[MAX];

int top = -1;

// Function Prototypes

void push();

void pop();

void display();

int main() {

int choice;

while (1) {

// Menu

printf("\nArray-based Stack Operations:\n");

printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);
 21

switch (choice) {

case 1: push(); break;

case 2: pop(); break;

case 3: display(); break;

case 4: printf("\nExiting Program.\n"); return 0;

default: printf("Invalid choice! Please try again.\n");

// Push operation

void push() {

int value;

if (top == MAX - 1) {

printf("Stack Overflow!\n");

} else {

printf("Enter the value to push: ");

scanf("%d", &value);

stack[++top] = value;

printf("%d pushed to stack.\n", value);

// Pop operation

void pop() {

if (top == -1) {

printf("Stack Underflow!\n");

} else {

printf("%d popped from stack.\n", stack[top--]);

 22

// Display stack elements

void display() {

if (top == -1) {

printf("Stack is empty.\n");

} else {

printf("Stack elements (top to bottom): ");

for (int i = top; i >= 0; i--) {

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

printf("\n");

Output and Results

• Output: The program displays options to push, pop, display, or exit the stack operations.

• Results: This program successfully performs stack operations using arrays, displaying stack
elements and handling overflow and underflow conditions appropriately.

Program 2: Stack Using Pointers

Aim

To implement stack operations (Push, Pop, Display) using pointers in C.

Program Logic

1. push(): Creates a new node and inserts it at the top of the stack.

2. pop(): Removes the top node if the stack is not empty.

3. display(): Shows all elements in the stack from top to bottom.

 23

#include <stdio.h>

#include <stdlib.h>

// Node structure for pointer-based stack

struct Node {

int data;

struct Node* next;

};

struct Node* top = NULL;

// Function Prototypes

void push();

void pop();

void display();

int main() {

int choice;

while (1) {

// Menu

printf("\nPointer-based Stack Operations:\n");

printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1: push(); break;

case 2: pop(); break;

 24

case 3: display(); break;

case 4: printf("\nExiting Program.\n"); return 0;

default: printf("Invalid choice! Please try again.\n");

// Push operation

void push() {

int value;

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

if (newNode == NULL) {

printf("Memory allocation failed. Stack Overflow!\n");

} else {

printf("Enter the value to push: ");

scanf("%d", &value);

newNode->data = value;

newNode->next = top;

top = newNode;

printf("%d pushed to stack.\n", value);

// Pop operation

void pop() {

if (top == NULL) {

printf("Stack Underflow!\n");

} else {
 25

struct Node* temp = top;

printf("%d popped from stack.\n", temp->data);

top = top->next;

free(temp);

// Display stack elements

void display() {

if (top == NULL) {

printf("Stack is empty.\n");

} else {

struct Node* temp = top;

printf("Stack elements (top to bottom): ");

while (temp != NULL) {

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

temp = temp->next;

printf("\n");

Output and Results

• Output: This program shows a menu with options to push, pop, display, or exit.

• Results: This program successfully performs stack operations using pointers, handling memory
dynamically and providing stack functionality.
 26

5. Write a program that implement Queue (its operations) using

i) Arrays ii) Pointers

Program 1: Queue Using Arrays

Aim

To implement queue operations (Enqueue, Dequeue, Display) using arrays in C.

Program Logic

1. enqueue(): Adds an element at the rear of the queue if it's not full.

2. dequeue(): Removes an element from the front if the queue is not empty.

3. display(): Shows all elements from front to rear.

#include <stdio.h>

#define MAX 5

// Array-based Queue

int queue[MAX];

int front = -1, rear = -1;

// Function Prototypes

void enqueue();

void dequeue();

void display();

int main() {

int choice;

while (1) {

// Menu

printf("\nArray-based Queue Operations:\n");

 27

printf("1. Enqueue\n2. Dequeue\n3. Display\n4. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1: enqueue(); break;

case 2: dequeue(); break;

case 3: display(); break;

case 4: printf("\nExiting Program.\n"); return 0;

default: printf("Invalid choice! Please try again.\n");

// Enqueue operation

void enqueue() {

int value;

if (rear == MAX - 1) {

printf("Queue Overflow!\n");

} else {

printf("Enter the value to enqueue: ");

scanf("%d", &value);

if (front == -1) front = 0;

queue[++rear] = value;

printf("%d enqueued to queue.\n", value);

// Dequeue operation
 28

void dequeue() {

if (front == -1 || front > rear) {

printf("Queue Underflow!\n");

} else {

printf("%d dequeued from queue.\n", queue[front++]);

if (front > rear) front = rear = -1;

// Display queue elements

void display() {

if (front == -1) {

printf("Queue is empty.\n");

} else {

printf("Queue elements (front to rear): ");

for (int i = front; i <= rear; i++) {

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

printf("\n");

Output and Results

• Output: The program displays options to enqueue, dequeue, display, or exit.

• Results: This program successfully performs queue operations using arrays, with overflow and
underflow checks.
 29

Program 2: Queue Using Pointers

Aim

To implement queue operations (Enqueue, Dequeue, Display) using pointers in C.

Program Logic

1. enqueue(): Creates a new node and adds it at the rear of the queue.

2. dequeue(): Removes the front node if the queue is not empty.

3. display(): Shows all elements from front to rear.

#include <stdio.h>

#include <stdlib.h>

// Node structure for pointer-based queue

struct Node {

int data;

struct Node* next;

};

struct Node* front = NULL;

struct Node* rear = NULL;

// Function Prototypes

void enqueue();

void dequeue();

void display();

int main() {

int choice;

while (1) {
 30

// Menu

printf("\nPointer-based Queue Operations:\n");

printf("1. Enqueue\n2. Dequeue\n3. Display\n4. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1: enqueue(); break;

case 2: dequeue(); break;

case 3: display(); break;

case 4: printf("\nExiting Program.\n"); return 0;

default: printf("Invalid choice! Please try again.\n");

// Enqueue operation

void enqueue() {

int value;

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

if (newNode == NULL) {

printf("Memory allocation failed. Queue Overflow!\n");

} else {

printf("Enter the value to enqueue: ");

scanf("%d", &value);

newNode->data = value;

newNode->next = NULL;
 31

if (rear == NULL) {

front = rear = newNode;

} else {

rear->next = newNode;

rear = newNode;

printf("%d enqueued to queue.\n", value);

// Dequeue operation

void dequeue() {

if (front == NULL) {

printf("Queue Underflow!\n");

} else {

struct Node* temp = front;

printf("%d dequeued from queue.\n", front->data);

front = front->next;

if (front == NULL) {

rear = NULL;

free(temp);

// Display queue elements

void display() {

if (front == NULL) {
 32

printf("Queue is empty.\n");

} else {

struct Node* temp = front;

printf("Queue elements (front to rear): ");

while (temp != NULL) {

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

temp = temp->next;

printf("\n");

Output and Results

• Output: This program shows a menu with options to enqueue, dequeue, display, or exit.

• Results: The program performs queue operations successfully using pointers, handling dynamic
memory and maintaining the front and rear nodes properly.

6. Write a program that implements the following sorting methods to sort a given list of integers

in ascending order

i) Quick sort ii) Heap sort iii) Merge sort

Program 1: Quick Sort

Aim

To implement the Quick Sort algorithm to sort a list of integers in ascending order.

Program Logic

Quick Sort: A divide-and-conquer algorithm that partitions the array around a pivot element and
recursively sorts the subarrays.
 33

#include <stdio.h>

void quickSort(int arr[], int low, int high);

int partition(int arr[], int low, int high);

int main() {

int n;

printf("Enter the number of elements: ");

scanf("%d", &n);

int arr[n];

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

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

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

quickSort(arr, 0, n - 1);

printf("Sorted array in ascending order:\n");

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

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

printf("\n");

return 0;

// Quick Sort function

 34

void quickSort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

// Partition function

int partition(int arr[], int low, int high) {

int pivot = arr[high];

int i = (low - 1);

for (int j = low; j < high; j++) {

if (arr[j] < pivot) {

i++;

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

int temp = arr[i + 1];

arr[i + 1] = arr[high];

arr[high] = temp;

return (i + 1);

}
 35

Program 2: Heap Sort

Aim

To implement the Heap Sort algorithm to sort a list of integers in ascending order.

Program Logic

Heap Sort: Builds a max heap from the array, then repeatedly extracts the maximum element and
rebuilds the heap.

#include <stdio.h>

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

void heapSort(int arr[], int n);

int main() {

int n;

printf("Enter the number of elements: ");

scanf("%d", &n);

int arr[n];

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

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

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

heapSort(arr, n);

printf("Sorted array in ascending order:\n");

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

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

 36

printf("\n");

return 0;

// Heap Sort function

void heapSort(int arr[], int n) {

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

heapify(arr, n, i);

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

int temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

heapify(arr, i, 0);

// Heapify function

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

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest]) {

largest = left;

}
 37

if (right < n && arr[right] > arr[largest]) {

largest = right;

if (largest != i) {

int temp = arr[i];

arr[i] = arr[largest];

arr[largest] = temp;

heapify(arr, n, largest);

Program 3: Merge Sort

Aim

To implement the Merge Sort algorithm to sort a list of integers in ascending order.

Program Logic

Merge Sort: A divide-and-conquer algorithm that divides the array into two halves, recursively
sorts them, and then merges the sorted halves.

#include <stdio.h>

void merge(int arr[], int left, int mid, int right);

void mergeSort(int arr[], int left, int right);

int main() {

int n;

printf("Enter the number of elements: ");

 38

scanf("%d", &n);

int arr[n];

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

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

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

mergeSort(arr, 0, n - 1);

printf("Sorted array in ascending order:\n");

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

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

printf("\n");

return 0;

// Merge Sort function

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

if (left < right) {

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

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

}
 39

// Merge function

void merge(int arr[], int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

int L[n1], R[n2];

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

L[i] = arr[left + i];

for (int j = 0; j < n2; j++) {

R[j] = arr[mid + 1 + j];

int i = 0, j = 0, k = left;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

k++;

while (i < n1) {

arr[k] = L[i];

i++;

k++;
 40

while (j < n2) {

arr[k] = R[j];

j++;

k++;

Output and Results

Each program takes an input list of integers, sorts it in ascending order, and displays the sorted list. The
output demonstrates that the sorting methods work correctly for each algorithm.

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

Program 1: Recursive Tree Traversal (With Runtime Input)

Aim

To implement recursive tree traversal methods (Preorder, Inorder, and Postorder) for a binary tree, with
the tree structure provided by the user at runtime.

Program Logic

1. Recursive Traversals: The traversal is done using recursive functions to visit each node.

o Preorder: Visit root, left subtree, right subtree.

o Inorder: Visit left subtree, root, right subtree.

o Postorder: Visit left subtree, right subtree, root.

#include <stdio.h>

#include <stdlib.h>

// Define structure for tree node

struct Node {
 41

int data;

struct Node* left;

struct Node* right;

};

// Function declarations

struct Node* createNode(int data);

void preorder(struct Node* root);

void inorder(struct Node* root);

void postorder(struct Node* root);

// Function to insert node

struct Node* insertNode(struct Node* root, int data) {

if (root == NULL) {

return createNode(data);

printf("Enter left or right for node %d (l/r): ", root->data);

char choice;

scanf(" %c", &choice); // Space before %c to handle newline character

if (choice == 'l' || choice == 'L') {

root->left = insertNode(root->left, data);

} else if (choice == 'r' || choice == 'R') {

root->right = insertNode(root->right, data);

return root;

int main() {

int n, rootValue;
 42

printf("Enter the root node value: ");

scanf("%d", &rootValue);

struct Node* root = createNode(rootValue);

printf("Enter the number of nodes to insert: ");

scanf("%d", &n);

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

int data;

printf("Enter node value to insert: ");

scanf("%d", &data);

root = insertNode(root, data);

printf("Preorder traversal: ");

preorder(root);

printf("\n");

printf("Inorder traversal: ");

inorder(root);

printf("\n");

printf("Postorder traversal: ");

postorder(root);

printf("\n");

return 0;
 43

// Create a new tree node

struct Node* createNode(int data) {

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

newNode->data = data;

newNode->left = newNode->right = NULL;

return newNode;

// Preorder Traversal (Root -> Left -> Right)

void preorder(struct Node* root) {

if (root != NULL) {

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

preorder(root->left);

preorder(root->right);

// Inorder Traversal (Left -> Root -> Right)

void inorder(struct Node* root) {

if (root != NULL) {

inorder(root->left);

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

inorder(root->right);

// Postorder Traversal (Left -> Right -> Root)

 44

void postorder(struct Node* root) {

if (root != NULL) {

postorder(root->left);

postorder(root->right);

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

Program 2: Non-Recursive Tree Traversal (With Runtime Input)

Aim

To implement non-recursive tree traversal methods (Preorder, Inorder, and Postorder) using a stack, with
the tree structure provided by the user at runtime.

Program Logic

1. Non-Recursive Traversals: We use a stack to simulate the recursion in the traversal process.

o Preorder: Root, left subtree, right subtree.

o Inorder: Left subtree, root, right subtree.

o Postorder: Left subtree, right subtree, root.

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

// Define structure for tree node

struct Node {

int data;

struct Node* left;

struct Node* right;

};
 45

// Define structure for stack

struct Stack {

struct Node** arr;

int top;

int capacity;

};

// Function declarations

struct Node* createNode(int data);

struct Stack* createStack(int capacity);

bool isEmpty(struct Stack* stack);

void push(struct Stack* stack, struct Node* node);

struct Node* pop(struct Stack* stack);

void preorder(struct Node* root);

void inorder(struct Node* root);

void postorder(struct Node* root);

// Function to insert node

struct Node* insertNode(struct Node* root, int data) {

if (root == NULL) {

return createNode(data);

printf("Enter left or right for node %d (l/r): ", root->data);

char choice;

scanf(" %c", &choice); // Space before %c to handle newline character

if (choice == 'l' || choice == 'L') {

root->left = insertNode(root->left, data);

} else if (choice == 'r' || choice == 'R') {

root->right = insertNode(root->right, data);

 46

return root;

int main() {

int n, rootValue;

printf("Enter the root node value: ");

scanf("%d", &rootValue);

struct Node* root = createNode(rootValue);

printf("Enter the number of nodes to insert: ");

scanf("%d", &n);

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

int data;

printf("Enter node value to insert: ");

scanf("%d", &data);

root = insertNode(root, data);

printf("Non-Recursive Preorder traversal: ");

preorder(root);

printf("\n");

printf("Non-Recursive Inorder traversal: ");

inorder(root);

printf("\n");
 47

printf("Non-Recursive Postorder traversal: ");

postorder(root);

printf("\n");

return 0;

// Create a new tree node

struct Node* createNode(int data) {

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

newNode->data = data;

newNode->left = newNode->right = NULL;

return newNode;

// Create a stack for nodes

struct Stack* createStack(int capacity) {

struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

stack->capacity = capacity;

stack->top = -1;

stack->arr = (struct Node**)malloc(stack->capacity * sizeof(struct Node*));

return stack;

// Check if the stack is empty

bool isEmpty(struct Stack* stack) {

return stack->top == -1;

}
 48

// Push a node onto the stack

void push(struct Stack* stack, struct Node* node) {

stack->arr[++stack->top] = node;

// Pop a node from the stack

struct Node* pop(struct Stack* stack) {

return stack->arr[stack->top--];

// Non-recursive Preorder Traversal

void preorder(struct Node* root) {

if (root == NULL) return;

struct Stack* stack = createStack(100);

push(stack, root);

while (!isEmpty(stack)) {

struct Node* node = pop(stack);

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

if (node->right != NULL) {

push(stack, node->right);

if (node->left != NULL) {

push(stack, node->left);

}
 49

// Non-recursive Inorder Traversal

void inorder(struct Node* root) {

if (root == NULL) return;

struct Stack* stack = createStack(100);

struct Node* curr = root;

while (curr != NULL || !isEmpty(stack)) {

while (curr != NULL) {

push(stack, curr);

curr = curr->left;

curr = pop(stack);

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

curr = curr->right;

// Non-recursive Postorder Traversal

void postorder(struct Node* root) {

if (root == NULL) return;

struct Stack* stack1 = createStack(100);

struct Stack* stack2 = createStack(100);

push(stack1, root);
 50

while (!isEmpty(stack1)) {

struct Node* node = pop(stack1);

push(stack2, node);

if (node->left != NULL) {

push(stack1, node->left);

if (node->right != NULL) {

push(stack1, node->right);

while (!isEmpty(stack2)) {

struct Node* node = pop(stack2);

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

Explanation:

1. The tree is built interactively:

o The root node is entered first.

o Then, users can specify where each new node should be inserted (left or right of a
specified node).

2. For each traversal (Preorder, Inorder, Postorder), the program displays the result after traversal
using either recursion or a stack for non-recursive traversal.

Sample Input/Output:

Example Input:

Enter the root node value: 1

Enter the number of nodes to insert: 6

 51

Enter node value to insert: 2

Enter left or right for node 1 (l/r): l

Enter node value to insert: 3

Enter left or right for node 1 (l/r): r

Enter node value to insert: 4

Enter left or right for node 2 (l/r): l

Enter node value to insert: 5

Enter left or right for node 2 (l/r): r

Enter node value to insert: 6

Enter left or right for node 3 (l/r): l

Enter node value to insert: 7

Enter left or right for node 3 (l/r): r

Example Output:

Non-Recursive Preorder traversal: 1 2 4 5 3 6 7

Non-Recursive Inorder traversal: 4 2 5 1 6 3 7

Non-Recursive Postorder traversal: 4 5 2 6 7 3 1

8. Write a program to implement

i) Binary Search tree ii) B Trees iii) B+ Trees iv) AVL

trees v) Red - Black trees

Program 1: Binary Search Tree (BST)

Aim

To implement a Binary Search Tree (BST) and perform the following operations:

• Insertion

• Traversal (Inorder, Preorder, Postorder)

Program Logic

1. Insertion: Insert a node into the BST by comparing its value with the current node.

2. Traversal: Implement Inorder, Preorder, and Postorder traversal recursively.

 52

#include <stdio.h>

#include <stdlib.h>

// Define structure for tree node

struct Node {

int data;

struct Node* left;

struct Node* right;

};

// Function declarations

struct Node* createNode(int data);

struct Node* insert(struct Node* root, int data);

void inorder(struct Node* root);

void preorder(struct Node* root);

void postorder(struct Node* root);

int main() {

struct Node* root = NULL;

int n, data;

printf("Enter the number of nodes to insert: ");

scanf("%d", &n);

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

printf("Enter node value: ");

scanf("%d", &data);

root = insert(root, data);

 53

printf("Inorder Traversal: ");

inorder(root);

printf("\n");

printf("Preorder Traversal: ");

preorder(root);

printf("\n");

printf("Postorder Traversal: ");

postorder(root);

printf("\n");

return 0;

// Create a new tree node

struct Node* createNode(int data) {

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

newNode->data = data;

newNode->left = newNode->right = NULL;

return newNode;

// Insert node into the BST

struct Node* insert(struct Node* root, int data) {

if (root == NULL) {

return createNode(data);
 54

if (data < root->data) {

root->left = insert(root->left, data);

} else {

root->right = insert(root->right, data);

return root;

// Inorder Traversal (Left -> Root -> Right)

void inorder(struct Node* root) {

if (root != NULL) {

inorder(root->left);

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

inorder(root->right);

// Preorder Traversal (Root -> Left -> Right)

void preorder(struct Node* root) {

if (root != NULL) {

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

preorder(root->left);

preorder(root->right);

// Postorder Traversal (Left -> Right -> Root)

void postorder(struct Node* root) {

 55

if (root != NULL) {

postorder(root->left);

postorder(root->right);

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

Output:

Enter the number of nodes to insert: 5

Enter node value: 10

Enter node value: 5

Enter node value: 15

Enter node value: 2

Enter node value: 7

Inorder Traversal: 2 5 7 10 15

Preorder Traversal: 10 5 2 7 15

Postorder Traversal: 2 7 5 15 10

Results:

• Inorder Traversal: 2 5 7 10 15

• Preorder Traversal: 10 5 2 7 15

• Postorder Traversal: 2 7 5 15 10

Program 2: B-Tree

Aim

To implement a B-Tree and perform the following operations:

• Insertion

• Traversal

Program Logic

1. Insertion: Insert a node into the B-tree by following the properties of the B-tree.
 56

2. Traversal: Perform inorder traversal of the B-tree.

#include <stdio.h>

#include <stdlib.h>

#define M 3 // Order of the B-tree (degree of each node)

// Define structure for B-Tree node

struct BTreeNode {

int keys[M - 1];

struct BTreeNode* children[M];

int numKeys;

int isLeaf;

};

// Function declarations

struct BTreeNode* createNode(int isLeaf);

void insert(struct BTreeNode** root, int key);

void splitChild(struct BTreeNode* parent, int index, struct BTreeNode* child);

void insertNonFull(struct BTreeNode* node, int key);

void inorder(struct BTreeNode* root);

int main() {

struct BTreeNode* root = NULL;

int n, data;

printf("Enter the number of nodes to insert: ");

scanf("%d", &n);
 57

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

printf("Enter node value: ");

scanf("%d", &data);

insert(&root, data);

printf("Inorder Traversal of B-Tree: ");

inorder(root);

printf("\n");

return 0;

// Create a new B-Tree node

struct BTreeNode* createNode(int isLeaf) {

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

node->isLeaf = isLeaf;

node->numKeys = 0;

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

node->children[i] = NULL;

return node;

// Insert a key into the B-Tree

void insert(struct BTreeNode** root, int key) {

if (*root == NULL) {

*root = createNode(1);

}
 58

if ((*root)->numKeys == M - 1) {

struct BTreeNode* newRoot = createNode(0);

newRoot->children[0] = *root;

splitChild(newRoot, 0, *root);

*root = newRoot;

insertNonFull(*root, key);

// Split a child node when it becomes full

void splitChild(struct BTreeNode* parent, int index, struct BTreeNode* child) {

struct BTreeNode* newChild = createNode(child->isLeaf);

newChild->numKeys = M / 2;

for (int i = 0; i < M / 2; i++) {

newChild->keys[i] = child->keys[i + M / 2];

if (!child->isLeaf) {

for (int i = 0; i <= M / 2; i++) {

newChild->children[i] = child->children[i + M / 2];

child->numKeys = M / 2;

for (int i = parent->numKeys; i > index; i--) {

parent->children[i + 1] = parent->children[i];
 59

parent->children[index + 1] = newChild;

for (int i = parent->numKeys - 1; i >= index; i--) {

parent->keys[i + 1] = parent->keys[i];

parent->keys[index] = child->keys[M / 2 - 1];

parent->numKeys++;

// Insert a key into a non-full node

void insertNonFull(struct BTreeNode* node, int key) {

int i = node->numKeys - 1;

if (node->isLeaf) {

while (i >= 0 && node->keys[i] > key) {

node->keys[i + 1] = node->keys[i];

i--;

node->keys[i + 1] = key;

node->numKeys++;

} else {

while (i >= 0 && node->keys[i] > key) {

i--;

i++;

if (node->children[i]->numKeys == M - 1) {

splitChild(node, i, node->children[i]);

if (node->keys[i] < key) {

 60

i++;

insertNonFull(node->children[i], key);

// Inorder Traversal of the B-Tree

void inorder(struct BTreeNode* root) {

if (root != NULL) {

for (int i = 0; i < root->numKeys; i++) {

inorder(root->children[i]);

printf("%d ", root->keys[i]);

inorder(root->children[root->numKeys]);

Output:

Enter the number of nodes to insert: 5

Enter node value: 10

Enter node value: 20

Enter node value: 5

Enter node value: 25

Enter node value: 15

Inorder Traversal of B-Tree: 5 10 15 20 25

Results:

• Inorder Traversal: 5 10 15 20 25
 61

Program 3: B+ Tree

Aim

To implement a B+ Tree and perform the following operations:

• Insertion

• Traversal

Program Logic

1. Insertion: Insert a node and maintain the properties of the B+ Tree.

2. Traversal: Perform inorder traversal of the B+ Tree.

#include <stdio.h>

#include <stdlib.h>

#define M 3 // Order of the B+ tree (degree of each node)

// Define structure for B+ Tree node

struct BPlusNode {

int keys[M - 1];

struct BPlusNode* children[M];

int numKeys;

int isLeaf;

struct BPlusNode* next; // For linked list of leaves

};

// Function declarations

struct BPlusNode* createNode(int isLeaf);

void insert(struct BPlusNode** root, int key);

void splitChild(struct BPlusNode* parent, int index, struct BPlusNode* child);

void insertNonFull(struct BPlusNode* node, int key);

void inorder(struct BPlusNode* root);

 62

int main() {

struct BPlusNode* root = NULL;

int n, data;

printf("Enter the number of nodes to insert: ");

scanf("%d", &n);

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

printf("Enter node value: ");

scanf("%d", &data);

insert(&root, data);

printf("Inorder Traversal of B+ Tree: ");

inorder(root);

printf("\n");

return 0;

// Create a new B+ Tree node

struct BPlusNode* createNode(int isLeaf) {

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

node->isLeaf = isLeaf;

node->numKeys = 0;

node->next = NULL;

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

node->children[i] = NULL;
 63

return node;

// Insert a key into the B+ Tree

void insert(struct BPlusNode** root, int key) {

if (*root == NULL) {

*root = createNode(1);

if ((*root)->numKeys == M - 1) {

struct BPlusNode* newRoot = createNode(0);

newRoot->children[0] = *root;

splitChild(newRoot, 0, *root);

*root = newRoot;

insertNonFull(*root, key);

// Split a child node when it becomes full

void splitChild(struct BPlusNode* parent, int index, struct BPlusNode* child) {

struct BPlusNode* newChild = createNode(child->isLeaf);

newChild->numKeys = M / 2;

for (int i = 0; i < M / 2; i++) {

newChild->keys[i] = child->keys[i + M / 2];

}
 64

if (!child->isLeaf) {

for (int i = 0; i <= M / 2; i++) {

newChild->children[i] = child->children[i + M / 2];

child->numKeys = M / 2;

for (int i = parent->numKeys; i > index; i--) {

parent->children[i + 1] = parent->children[i];

parent->children[index + 1] = newChild;

for (int i = parent->numKeys - 1; i >= index; i--) {

parent->keys[i + 1] = parent->keys[i];

parent->keys[index] = child->keys[M / 2 - 1];

parent->numKeys++;

// Insert a key into a non-full node

void insertNonFull(struct BPlusNode* node, int key) {

int i = node->numKeys - 1;

if (node->isLeaf) {

while (i >= 0 && node->keys[i] > key) {

node->keys[i + 1] = node->keys[i];

i--;

node->keys[i + 1] = key;
 65

node->numKeys++;

} else {

while (i >= 0 && node->keys[i] > key) {

i--;

i++;

if (node->children[i]->numKeys == M - 1) {

splitChild(node, i, node->children[i]);

if (node->keys[i] < key) {

i++;

insertNonFull(node->children[i], key);

// Inorder Traversal of the B+ Tree

void inorder(struct BPlusNode* root) {

if (root != NULL) {

for (int i = 0; i < root->numKeys; i++) {

inorder(root->children[i]);

printf("%d ", root->keys[i]);

inorder(root->children[root->numKeys]);

Output:

Enter the number of nodes to insert: 5

Enter node value: 10

 66

Enter node value: 20

Enter node value: 5

Enter node value: 25

Enter node value: 15

Inorder Traversal of B+ Tree: 5 10 15 20 25

Results:

• Inorder Traversal: 5 10 15 20 25

Program 4: AVL Tree

Aim

To implement an AVL Tree (a self-balancing binary search tree) and perform the following operations:

• Insertion

• Traversal (Inorder, Preorder, Postorder)

Program Logic

1. Insertion: Insert nodes into the AVL Tree while ensuring that the tree remains balanced after each
insertion.

2. Balancing: Perform rotations (left and right) when necessary to maintain the AVL property (the
height of the left and right subtrees can differ by at most 1).

3. Traversal: Implement Inorder, Preorder, and Postorder traversal.

#include <stdio.h>

#include <stdlib.h>

// Define structure for AVL Tree node

struct Node {

int data;

struct Node* left;

 67

struct Node* right;

int height;

};

// Function declarations

struct Node* createNode(int data);

int height(struct Node* node);

int max(int a, int b);

int getBalance(struct Node* node);

struct Node* rightRotate(struct Node* y);

struct Node* leftRotate(struct Node* x);

struct Node* insert(struct Node* node, int data);

void inorder(struct Node* root);

void preorder(struct Node* root);

void postorder(struct Node* root);

int main() {

struct Node* root = NULL;

int n, data;

printf("Enter the number of nodes to insert: ");

scanf("%d", &n);

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

printf("Enter node value: ");

scanf("%d", &data);

root = insert(root, data);

}
 68

printf("Inorder Traversal: ");

inorder(root);

printf("\n");

printf("Preorder Traversal: ");

preorder(root);

printf("\n");

printf("Postorder Traversal: ");

postorder(root);

printf("\n");

return 0;

// Create a new AVL Tree node

struct Node* createNode(int data) {

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

node->data = data;

node->left = node->right = NULL;

node->height = 1; // New node is initially at height 1

return node;

// Get the height of the node

int height(struct Node* node) {

if (node == NULL)

return 0;

return node->height;
 69

// Get the maximum of two numbers

int max(int a, int b) {

return (a > b) ? a : b;

// Get the balance factor of the node

int getBalance(struct Node* node) {

if (node == NULL)

return 0;

return height(node->left) - height(node->right);

// Right rotation

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;

// Left rotation
 70

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;

// Insert a node into the AVL tree

struct Node* insert(struct Node* node, int data) {

if (node == NULL)

return createNode(data);

if (data < node->data)

node->left = insert(node->left, data);

else if (data > node->data)

node->right = insert(node->right, data);

else

return node;

node->height = 1 + max(height(node->left), height(node->right));

int balance = getBalance(node);

 71

if (balance > 1 && data < node->left->data) {

return rightRotate(node);

if (balance < -1 && data > node->right->data) {

return leftRotate(node);

if (balance > 1 && data > node->left->data) {

node->left = leftRotate(node->left);

return rightRotate(node);

if (balance < -1 && data < node->right->data) {

node->right = rightRotate(node->right);

return leftRotate(node);

return node;

// Inorder Traversal

void inorder(struct Node* root) {

if (root != NULL) {

inorder(root->left);

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

inorder(root->right);

}
 72

// Preorder Traversal

void preorder(struct Node* root) {

if (root != NULL) {

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

preorder(root->left);

preorder(root->right);

// Postorder Traversal

void postorder(struct Node* root) {

if (root != NULL) {

postorder(root->left);

postorder(root->right);

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

Output:

Enter the number of nodes to insert: 5

Enter node value: 10

Enter node value: 20

Enter node value: 5

Enter node value: 30

Enter node value: 25

Inorder Traversal: 5 10 20 25 30

Preorder Traversal: 20 10 5 25 30

Postorder Traversal: 5 10 25 30 20
 73

Results:

• Inorder Traversal: 5 10 20 25 30

• Preorder Traversal: 20 10 5 25 30

• Postorder Traversal: 5 10 25 30 20

Program 5: Red-Black Tree

Aim

To implement a Red-Black Tree and perform the following operations:

• Insertion

• Traversal

Program Logic

1. Insertion: Insert a node into the tree and then fix any violations of the Red-Black Tree properties
(color of the nodes, root properties, and balancing).

2. Traversal: Perform inorder traversal.

Red-Black Tree Properties:

1. Every node is either red or black.

2. The root is always black.

3. Red nodes cannot have red children (no two consecutive red nodes).

4. Every path from a node to its descendant NULL nodes must have the same number of black nodes.

5. Newly inserted nodes are always red.

Operations:

1. Insertion: Insert nodes while ensuring the Red-Black properties are maintained using rotations
(left and right) and color flips.

2. Traversal: Implement an inorder traversal.

Approach:

1. Insert a new node.

2. Rebalance the tree by checking the violation of the Red-Black properties and performing
necessary rotations.

3. Perform an inorder traversal to verify the tree structure.

 74

Program: Red-Black Tree

#include <stdio.h>

#include <stdlib.h>

#define RED 0

#define BLACK 1

// Define structure for Red-Black Tree node

struct Node {

int data;

struct Node* left;

struct Node* right;

struct Node* parent;

int color; // RED or BLACK

};

// Create a new Red-Black Tree node

struct Node* createNode(int data) {

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

newNode->data = data;

newNode->left = newNode->right = newNode->parent = NULL;

newNode->color = RED; // New nodes are always red

return newNode;

// Left rotate the subtree rooted at x

void leftRotate(struct Node** root, struct Node* x) {

struct Node* y = x->right;

 75

x->right = y->left;

if (y->left != NULL) {

y->left->parent = x;

y->parent = x->parent;

if (x->parent == NULL) {

*root = y;

} else if (x == x->parent->left) {

x->parent->left = y;

} else {

x->parent->right = y;

y->left = x;

x->parent = y;

// Right rotate the subtree rooted at y

void rightRotate(struct Node** root, struct Node* y) {

struct Node* x = y->left;

y->left = x->right;

if (x->right != NULL) {

x->right->parent = y;

x->parent = y->parent;

if (y->parent == NULL) {

*root = x;

} else if (y == y->parent->left) {

y->parent->left = x;

} else {
 76

y->parent->right = x;

x->right = y;

y->parent = x;

// Fix violations of the Red-Black Tree properties after insertion

void fixInsert(struct Node** root, struct Node* node) {

struct Node* uncle;

while (node != *root && node->parent->color == RED) {

if (node->parent == node->parent->parent->left) {

uncle = node->parent->parent->right;

if (uncle != NULL && uncle->color == RED) {

node->parent->color = BLACK;

uncle->color = BLACK;

node->parent->parent->color = RED;

node = node->parent->parent;

} else {

if (node == node->parent->right) {

node = node->parent;

leftRotate(root, node);

node->parent->color = BLACK;

node->parent->parent->color = RED;

rightRotate(root, node->parent->parent);

} else {

uncle = node->parent->parent->left;
 77

if (uncle != NULL && uncle->color == RED) {

node->parent->color = BLACK;

uncle->color = BLACK;

node->parent->parent->color = RED;

node = node->parent->parent;

} else {

if (node == node->parent->left) {

node = node->parent;

rightRotate(root, node);

node->parent->color = BLACK;

node->parent->parent->color = RED;

leftRotate(root, node->parent->parent);

(*root)->color = BLACK;

// Insert a node into the Red-Black Tree

void insert(struct Node** root, int data) {

struct Node* newNode = createNode(data);

struct Node* y = NULL;

struct Node* x = *root;

while (x != NULL) {

y = x;

if (newNode->data < x->data) {

x = x->left;
 78

} else {

x = x->right;

newNode->parent = y;

if (y == NULL) {

*root = newNode;

} else if (newNode->data < y->data) {

y->left = newNode;

} else {

y->right = newNode;

fixInsert(root, newNode);

// Inorder Traversal

void inorder(struct Node* root) {

if (root != NULL) {

inorder(root->left);

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

inorder(root->right);

int main() {

struct Node* root = NULL;

int n, data;
 79

printf("Enter the number of nodes to insert: ");

scanf("%d", &n);

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

printf("Enter node value: ");

scanf("%d", &data);

insert(&root, data);

printf("Inorder Traversal: ");

inorder(root);

printf("\n");

return 0;

Output:

Enter the number of nodes to insert: 5

Enter node value: 10

Enter node value: 20

Enter node value: 15

Enter node value: 5

Enter node value: 25

Inorder Traversal: 5 10 15 20 25

Results:

• Inorder Traversal: 5 10 15 20 25
 80

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

Aim

To implement graph traversal methods:

1. Breadth-First Search (BFS)

2. Depth-First Search (DFS)

The graph will be represented using an adjacency matrix, and the traversal methods will be implemented
using recursive and iterative approaches.

Program Logic

1. BFS (Breadth-First Search): It explores the graph level by level starting from a given vertex. BFS
uses a queue to explore each level in the graph.

2. DFS (Depth-First Search): It explores as deep as possible along each branch before backtracking.
DFS uses recursion or a stack to explore nodes in depth first.

Program 1: BFS (Breadth-First Search)

Aim:

To implement Breadth-First Search (BFS) on a graph represented using an adjacency matrix. The BFS will
explore the graph level by level starting from a given vertex.

Program Logic:

1. Initialize a queue and an array to track visited nodes.

2. Start at the specified vertex and mark it as visited.

3. Use the queue to explore all neighbors of the current vertex, and visit unvisited nodes.

#include <stdio.h>

#include <stdlib.h>

#define MAX_VERTICES 10

// Graph structure

struct Graph {

int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // Adjacency matrix

 81

int numVertices; // Number of vertices

};

// Function declarations

void initGraph(struct Graph* graph, int vertices);

void addEdge(struct Graph* graph, int start, int end);

void BFS(struct Graph* graph, int startVertex);

// Main function

int main() {

struct Graph graph;

int vertices, edges, startVertex, u, v;

printf("Enter the number of vertices: ");

scanf("%d", &vertices);

initGraph(&graph, vertices);

printf("Enter the number of edges: ");

scanf("%d", &edges);

printf("Enter the edges (u v): \n");

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

scanf("%d %d", &u, &v);

addEdge(&graph, u, v);

printf("Enter the starting vertex for BFS: ");

scanf("%d", &startVertex);
 82

printf("\nBreadth-First Search (BFS) starting from vertex %d:\n", startVertex);

BFS(&graph, startVertex);

return 0;

// Initialize the graph with no edges

void initGraph(struct Graph* graph, int vertices) {

graph->numVertices = vertices;

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

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

graph->adjMatrix[i][j] = 0;

// Add an edge between vertices u and v (undirected graph)

void addEdge(struct Graph* graph, int u, int v) {

graph->adjMatrix[u][v] = 1;

graph->adjMatrix[v][u] = 1; // Since it's an undirected graph

// BFS algorithm

void BFS(struct Graph* graph, int startVertex) {

int visited[MAX_VERTICES] = {0};

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

visited[startVertex] = 1;
 83

queue[rear++] = startVertex;

printf("BFS Traversal: ");

while (front < rear) {

int currentVertex = queue[front++];

printf("%d ", currentVertex);

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

if (graph->adjMatrix[currentVertex][i] == 1 && !visited[i]) {

queue[rear++] = i;

visited[i] = 1;

printf("\n");

Output for BFS Program:

Enter the number of vertices: 6

Enter the number of edges: 7

Enter the edges (u v):

01

02

13

14

24

35

45
 84

Enter the starting vertex for BFS: 0

Breadth-First Search (BFS) starting from vertex 0:

BFS Traversal: 0 1 2 3 4 5

Program 2: DFS (Depth-First Search)

Aim:

To implement Depth-First Search (DFS) on a graph represented using an adjacency matrix. The DFS will
explore the graph by going deep into the graph as far as possible along each branch before backtracking.

Program Logic:

1. Use a recursive approach to visit each node.

2. Track visited nodes using an array.

3. Explore the graph by visiting the unvisited adjacent nodes from each vertex.

#include <stdio.h>

#include <stdlib.h>

#define MAX_VERTICES 10

// Graph structure

struct Graph {

int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // Adjacency matrix

int numVertices; // Number of vertices

};

// Function declarations

void initGraph(struct Graph* graph, int vertices);

void addEdge(struct Graph* graph, int start, int end);

void DFS(struct Graph* graph, int startVertex, int visited[]);

 85

// Main function

int main() {

struct Graph graph;

int vertices, edges, startVertex, u, v;

printf("Enter the number of vertices: ");

scanf("%d", &vertices);

initGraph(&graph, vertices);

printf("Enter the number of edges: ");

scanf("%d", &edges);

printf("Enter the edges (u v): \n");

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

scanf("%d %d", &u, &v);

addEdge(&graph, u, v);

printf("Enter the starting vertex for DFS: ");

scanf("%d", &startVertex);

printf("\nDepth-First Search (DFS) starting from vertex %d:\n", startVertex);

int visited[MAX_VERTICES] = {0}; // Initialize visited array

DFS(&graph, startVertex, visited);

return 0;

}
 86

// Initialize the graph with no edges

void initGraph(struct Graph* graph, int vertices) {

graph->numVertices = vertices;

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

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

graph->adjMatrix[i][j] = 0;

// Add an edge between vertices u and v (undirected graph)

void addEdge(struct Graph* graph, int u, int v) {

graph->adjMatrix[u][v] = 1;

graph->adjMatrix[v][u] = 1; // Since it's an undirected graph

// DFS algorithm (recursive)

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

visited[startVertex] = 1;

printf("%d ", startVertex);

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

if (graph->adjMatrix[startVertex][i] == 1 && !visited[i]) {

DFS(graph, i, visited);

}
 87

Output for DFS Program:

Enter the number of vertices: 6

Enter the number of edges: 7

Enter the edges (u v):

01

02

13

14

24

35

45

Enter the starting vertex for DFS: 0

Depth-First Search (DFS) starting from vertex 0:

DFS Traversal: 0 1 3 5 4 2

Explanation:

• BFS uses a queue to explore nodes level by level starting from a given vertex.

• DFS uses recursion to explore as deeply as possible along each branch before backtracking.

Both BFS and DFS are essential algorithms in graph theory, where BFS is used in problems like finding the
shortest path in an unweighted graph, and DFS is useful for problems like topological sorting and finding
connected components.

Conclusion:

• BFS explores nodes in level-order.

• DFS explores nodes in a depth-first manner.

 88

10. Implement a Pattern matching algorithms using Boyer- Moore, Knuth-Morris-Pratt

Program 1: Boyer-Moore Algorithm for Pattern Matching

Aim:

To implement the Boyer-Moore algorithm for pattern matching, which efficiently searches for a substring
(pattern) in a given text by scanning from right to left of the pattern.

Program Logic:

1. Boyer-Moore Algorithm uses two heuristics:

o Bad Character Heuristic: If a mismatch occurs, the pattern is shifted so that the
mismatched character in the text aligns with the last occurrence of that character in the
pattern.

o Good Suffix Heuristic: If a mismatch occurs, the pattern is shifted to align the longest suffix
of the matched part with the pattern.

#include <stdio.h>

#include <string.h>

#define ALPHABET_SIZE 256 // Total number of possible characters in text

// Function to preprocess the pattern and calculate the bad character heuristic

void badCharacterHeuristic(char* pattern, int m, int badChar[ALPHABET_SIZE]) {

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

badChar[i] = -1;

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

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

}
 89

// Boyer-Moore algorithm for pattern matching

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

int m = strlen(pattern);

int n = strlen(text);

int badChar[ALPHABET_SIZE];

// Preprocess the pattern

badCharacterHeuristic(pattern, m, badChar);

int s = 0; // shift of the pattern with respect to the text

while (s <= n - m) {

int j = m - 1;

// Find the rightmost character in the pattern that matches the text

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

j--;

// If pattern is found

if (j < 0) {

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

s += (s + m < n) ? m - badChar[(int)text[s + m]] : 1;

} else {

s += (j - badChar[(int)text[s + j]] > 1) ? j - badChar[(int)text[s + j]] : 1;

}
 90

int main() {

char text[100], pattern[50];

// Taking input from user

printf("Enter the text: ");

fgets(text, sizeof(text), stdin);

printf("Enter the pattern: ");

fgets(pattern, sizeof(pattern), stdin);

// Remove the newline character from the input

text[strcspn(text, "\n")] = 0;

pattern[strcspn(pattern, "\n")] = 0;

printf("\nBoyer-Moore Pattern Matching Algorithm:\n");

boyerMooreSearch(text, pattern);

return 0;

Output for Boyer-Moore Program:

Enter the text: ABABDABACDABABCABAB

Enter the pattern: ABABCABAB

Boyer-Moore Pattern Matching Algorithm:

Pattern found at index 10

 91

Program 2: Knuth-Morris-Pratt (KMP) Algorithm for Pattern Matching

Aim:

To implement the Knuth-Morris-Pratt (KMP) algorithm for pattern matching, which improves the
efficiency of substring search by using a preprocessing phase to build a partial match table (also called
"prefix table").

Program Logic:

1. The KMP algorithm uses a partial match table to avoid unnecessary re-evaluations.

2. This table helps in skipping the comparisons of characters that have already been matched and
reduces the time complexity to O(n + m).

#include <stdio.h>

#include <string.h>

// Function to preprocess the pattern and calculate the longest prefix suffix array

void computeLPSArray(char* pattern, int m, int lps[]) {

int length = 0; // Length of the previous longest prefix suffix

lps[0] = 0; // LPS[0] is always 0

int i = 1;

while (i < m) {

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

length++;

lps[i] = length;

i++;

} else {

if (length != 0) {

length = lps[length - 1];

} else {
 92

lps[i] = 0;

i++;

// Knuth-Morris-Pratt (KMP) pattern matching algorithm

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

int m = strlen(pattern);

int n = strlen(text);

int lps[m]; // Longest Prefix Suffix array

// Preprocess the pattern to get the LPS array

computeLPSArray(pattern, m, lps);

int i = 0; // index for text

int j = 0; // index for pattern

while (i < n) {

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

i++;

j++;

if (j == m) {

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

j = lps[j - 1];

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

 93

if (j != 0) {

j = lps[j - 1];

} else {

i++;

int main() {

char text[100], pattern[50];

// Taking input from user

printf("Enter the text: ");

fgets(text, sizeof(text), stdin);

printf("Enter the pattern: ");

fgets(pattern, sizeof(pattern), stdin);

// Remove the newline character from the input

text[strcspn(text, "\n")] = 0;

pattern[strcspn(pattern, "\n")] = 0;

printf("\nKnuth-Morris-Pratt (KMP) Pattern Matching Algorithm:\n");

KMPsearch(text, pattern);

return 0;

Output for KMP Program:

 94

Enter the text: ABABDABACDABABCABAB

Enter the pattern: ABABCABAB

Knuth-Morris-Pratt (KMP) Pattern Matching Algorithm:

Pattern found at index 10

Results and Conclusion:

• Boyer-Moore Algorithm:

o The Boyer-Moore algorithm is faster in practice than other pattern matching algorithms
because it skips over large sections of the text based on mismatches and the bad character
heuristic.

o The output shows the index where the pattern is found.

• Knuth-Morris-Pratt (KMP) Algorithm:

o The KMP algorithm avoids redundant comparisons by using the LPS (Longest Prefix Suffix)
array.

o It efficiently matches patterns in a single pass, with a time complexity of O(n + m), where
n is the length of the text and m is the length of the pattern.

Both algorithms are more efficient than brute force algorithms, especially for larger texts.