lDATA STRUCTURES LAB

1. Write a program to search for an element in an array using binary and linear search.

#include <stdio.h>

// Function for Linear Search

int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key)
return i; // Element found, return index
}
return -1; // Element not found
}

// Function for Binary Search (Iterative)

int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;

if (arr[mid] == key)
return mid; // Element found, return index
else if (arr[mid] < key)
left = mid + 1; // Search in right half
else
right = mid - 1; // Search in left half
}
return -1; // Element not found
}

int main() {
int n, key, choice;

// Taking input for array size

printf("Enter the number of elements in the array: ");
scanf("%d", &n);

int arr[n];

// Taking input for array elements

printf("Enter %d elements in sorted order for Binary Search: ", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);

// Taking input for element to search

By Prof. Amogha A R
 printf("Enter the element to search: ");
scanf("%d", &key);

// Performing Linear Search

int linResult = linearSearch(arr, n, key);
if (linResult != -1)
printf("Linear Search: Element found at index %d\n",
linResult);
else
printf("Linear Search: Element not found\n");

// Performing Binary Search

int binResult = binarySearch(arr, 0, n - 1, key);
if (binResult != -1)
printf("Binary Search: Element found at index %d\n",
binResult);
else
printf("Binary Search: Element not found\n");

return 0;
}

How it Works?

2. The user enters the array size and elements (in sorted order for binary search).
3. The program asks for the element to search.
4. Linear Search scans each element one by one.
5. Binary Search efficiently finds the element in a sorted array.
6. The program displays the index if found or a "not found" message.

By Prof. Amogha A R
By Prof. Amogha A R
By Prof. Amogha A R
2. Write a program to sort list of n numbers using Bubble Sort algorithms.

#include <stdio.h>

// Function to perform Bubble Sort

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

// Function to print the array

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

int main() {
int n;

// Taking input for number of elements

printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];

// Taking input for array elements

printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);

// Sorting the array using Bubble Sort

bubbleSort(arr, n);

// Displaying sorted array

printf("Sorted array: ");
printArray(arr, n);

By Prof. Amogha A R
 return 0;
}

3. Perform the Insertion and Selection Sort on the input {75,8,1,16,48,3,7,0} and display the
output in descending order.
By Prof. Amogha A R
#include <stdio.h>

// Function for Insertion Sort (Descending Order)

void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;

// Move elements that are smaller than key one position ahead
while (j >= 0 && arr[j] < key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

// Function for Selection Sort (Descending Order)

void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int maxIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[maxIdx]) {
maxIdx = j;
}
}
// Swap max element with the first element
int temp = arr[maxIdx];
arr[maxIdx] = arr[i];
arr[i] = temp;
}
}

// Function to print array

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

int main() {
int arr1[] = {75, 8, 1, 16, 48, 3, 7, 0};
int arr2[] = {75, 8, 1, 16, 48, 3, 7, 0};
int n = sizeof(arr1) / sizeof(arr1[0]);

By Prof. Amogha A R
 // Sorting using Insertion Sort
insertionSort(arr1, n);
printf("Sorted array using Insertion Sort (Descending Order): ");
printArray(arr1, n);

// Sorting using Selection Sort

selectionSort(arr2, n);
printf("Sorted array using Selection Sort (Descending Order): ");
printArray(arr2, n);

return 0;
}

4. Write a program to insert the elements {61,16,8,27} into singly linked list and delete
8,61,27 from the list. Display your list after each insertion and deletion.

By Prof. Amogha A R
#include <stdio.h>
#include <stdlib.h>

// Structure for a Node in Linked List

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

// Function to insert a node at the end of the linked list

void insert(struct Node** head, int value) {
struct Node* 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("Inserted: %d\n", value);
}

// Function to delete a node by value

void deleteNode(struct Node** head, int value) {
struct Node* temp = *head, *prev = NULL;

// If head node itself holds the value to be deleted

if (temp != NULL && temp->data == value) {
*head = temp->next;
free(temp);
printf("Deleted: %d\n", value);
return;
}

// Search for the value to be deleted

while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
}

// If value was not found

if (temp == NULL) {
printf("Value %d not found in the list.\n", value);
By Prof. Amogha A R
 return;
}

// Unlink the node

prev->next = temp->next;
free(temp);
printf("Deleted: %d\n", value);
}

// Function to display the linked list

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

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

// Inserting elements
insert(&head, 61);
display(head);

insert(&head, 16);
display(head);

insert(&head, 8);
display(head);

insert(&head, 27);
display(head);

// Deleting elements
deleteNode(&head, 8);
display(head);

deleteNode(&head, 61);
display(head);

deleteNode(&head, 27);
display(head);

return 0;
By Prof. Amogha A R
 }

5. Write a program to insert the elements {45, 34, 10, 63,3} into linear queue and delete
three elements from the list. Display your list after each insertion and deletion.

By Prof. Amogha A R
#include <stdio.h>
#define SIZE 5 // Define the maximum size of the queue

int queue[SIZE]; // Array to store the queue elements

int front = -1, rear = -1; // Initialize front and rear pointers

// Function to insert an element into the queue

void enqueue(int value) {
if (rear == SIZE - 1) {
printf("Queue is full! Cannot insert %d\n", value);
return;
}
if (front == -1) // If queue is empty
front = 0;
queue[++rear] = value;
printf("Inserted: %d\n", value);
}

// Function to delete an element from the queue

void dequeue() {
if (front == -1 || front > rear) {
printf("Queue is empty! Cannot delete.\n");
return;
}
printf("Deleted: %d\n", queue[front]);
front++;
}

// Function to display the queue

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

int main() {
// Insert elements into the queue
enqueue(45);
display();

enqueue(34);
display();
By Prof. Amogha A R
 enqueue(10);
display();

enqueue(63);
display();

enqueue(3);
display();

// Delete three elements

dequeue();
display();

dequeue();
display();

dequeue();
display();

return 0;
}

By Prof. Amogha A R
By Prof. Amogha A R
6. Write a program to simulate the working of Circular queue using an array.

#include <stdio.h>
#define SIZE 5 // Define the maximum size of the queue

int queue[SIZE]; // Array to store the queue elements

int front = -1, rear = -1; // Initialize front and rear pointers

// Function to insert an element into the circular queue

void enqueue(int value) {
if ((rear + 1) % SIZE == front) { // Queue is full
printf("Queue is full! Cannot insert %d\n", value);
return;
}
if (front == -1) // If queue is initially empty
front = 0;
rear = (rear + 1) % SIZE; // Circular increment
queue[rear] = value;
printf("Inserted: %d\n", value);
}

// Function to delete an element from the circular queue

void dequeue() {
if (front == -1) { // Queue is empty
printf("Queue is empty! Cannot delete.\n");
return;
}
printf("Deleted: %d\n", queue[front]);
if (front == rear) { // Only one element was present
front = rear = -1;
} else {
front = (front + 1) % SIZE; // Circular increment
}
}

// Function to display the queue

void display() {
if (front == -1) {
printf("Queue is empty!\n");
return;
}
printf("Current Queue: ");
int i = front;
while (1) {
printf("%d ", queue[i]);
if (i == rear)
By Prof. Amogha A R
 break;
i = (i + 1) % SIZE;
}
printf("\n");
}

int main() {
// Insert elements into the circular queue
enqueue(10);
display();

enqueue(20);
display();

enqueue(30);
display();

enqueue(40);
display();

enqueue(50);
display();

// Queue is now full, next insertion should fail

enqueue(60);

// Delete elements from the circular queue

dequeue();
display();

dequeue();
display();

// Insert again to check circular behavior

enqueue(60);
display();

enqueue(70);
display();

return 0;
}

By Prof. Amogha A R
By Prof. Amogha A R
By Prof. Amogha A R
7. Write a program to insert the elements {61,16,8,27} into ordered singly linked list and
delete 8,61,27 from the list. Display your list after each insertion and deletion.

Insert elements {61, 16, 8, 27} in sorted order.

Delete elements 8, 61, 27 from the list.
Display the list after each insertion and deletion.

8. #include <stdio.h>
9. #include <stdlib.h>
10.
11. // Structure for a node in the linked list
12. struct Node {
13. int data;
14. struct Node* next;
15. };
16.
17. // Function to insert a node into the linked list in sorted order
18. void insertOrdered(struct Node** head, int value) {
19. struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node));
20. newNode->data = value;
21. newNode->next = NULL;
22.
23. if (*head == NULL || (*head)->data >= value) {
24. // Insert at the beginning if list is empty or value is
the smallest
25. newNode->next = *head;
26. *head = newNode;
27. } else {
28. // Find the correct position
29. struct Node* current = *head;
30. while (current->next != NULL && current->next->data <
value) {
31. current = current->next;
32. }
33. newNode->next = current->next;
34. current->next = newNode;
35. }
36. printf("Inserted: %d\n", value);
37. }
38.
39. // Function to delete a node from the linked list
40. void deleteNode(struct Node** head, int value) {
41. struct Node* temp = *head, *prev = NULL;
42.
By Prof. Amogha A R
43. // If the head node itself holds the value
44. if (temp != NULL && temp->data == value) {
45. *head = temp->next;
46. free(temp);
47. printf("Deleted: %d\n", value);
48. return;
49. }
50.
51. // Search for the node
52. while (temp != NULL && temp->data != value) {
53. prev = temp;
54. temp = temp->next;
55. }
56.
57. // If the value is not in the list
58. if (temp == NULL) {
59. printf("Value %d not found in the list!\n", value);
60. return;
61. }
62.
63. // Unlink the node
64. prev->next = temp->next;
65. free(temp);
66. printf("Deleted: %d\n", value);
67. }
68.
69. // Function to display the linked list
70. void display(struct Node* head) {
71. if (head == NULL) {
72. printf("List is empty!\n");
73. return;
74. }
75. printf("Current List: ");
76. while (head != NULL) {
77. printf("%d -> ", head->data);
78. head = head->next;
79. }
80. printf("NULL\n");
81. }
82.
83. int main() {
84. struct Node* head = NULL;
85.
86. // Insert elements in sorted order
87. insertOrdered(&head, 61);
88. display(head);
89.
By Prof. Amogha A R
90. insertOrdered(&head, 16);
91. display(head);
92.
93. insertOrdered(&head, 8);
94. display(head);
95.
96. insertOrdered(&head, 27);
97. display(head);
98.
99. // Delete elements from the list
100. deleteNode(&head, 8);
101. display(head);
102.
103. deleteNode(&head, 61);
104. display(head);
105.
106. deleteNode(&head, 27);
107. display(head);
108.
109. return 0;
110. }
111.

By Prof. Amogha A R
By Prof. Amogha A R
8. Write a program for Tower of Honoi problem using recursion.

#include <stdio.h>

// Function to solve Tower of Hanoi

void towerOfHanoi(int n, char source, char auxiliary, char destination)
{
if (n == 1) {
printf("Move disk 1 from %c to %c\n", source, destination);
return;
}

// Move n-1 disks from source to auxiliary

towerOfHanoi(n - 1, source, destination, auxiliary);

// Move the nth disk from source to destination

printf("Move disk %d from %c to %c\n", n, source, destination);

// Move n-1 disks from auxiliary to destination

towerOfHanoi(n - 1, auxiliary, source, destination);
}

int main() {
int n; // Number of disks
printf("Enter the number of disks: ");
scanf("%d", &n);

// Call the function to solve Tower of Hanoi

towerOfHanoi(n, 'A', 'B', 'C');

return 0;
}

By Prof. Amogha A R
By Prof. Amogha A R
9. Write recursive program to find GCD of 3 numbers.

Step-by-Step Explanation (for num1 = 12, num2 = 15, num3 = 21):

#include <stdio.h>

// Recursive function to find GCD of two numbers

int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}

// Function to find GCD of three numbers

int gcd_of_three(int a, int b, int c) {
return gcd(a, gcd(b, c));

By Prof. Amogha A R
}

int main() {
int num1, num2, num3;

// Input three numbers

printf("Enter three numbers: ");
scanf("%d %d %d", &num1, &num2, &num3);

// Compute and display GCD

printf("GCD of %d, %d, and %d is: %d\n", num1, num2, num3,
gcd_of_three(num1, num2, num3));

return 0;
}

By Prof. Amogha A R
10. Write a program to demonstrate working of stack using linked list.

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

// Define a node structure

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

// Initialize top pointer

struct Node* top = NULL;

// Function to push an element onto the stack

void push(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Stack Overflow! No memory available.\n");
return;
}
newNode->data = value;
newNode->next = top;
top = newNode;

By Prof. Amogha A R
 printf("%d pushed to stack.\n", value);
}

// Function to pop an element from the stack

void pop() {
if (top == NULL) {
printf("Stack Underflow! No elements to pop.\n");
return;
}
struct Node* temp = top;
printf("%d popped from stack.\n", top->data);
top = top->next;
free(temp);
}

// Function to get the top element

void peek() {
if (top == NULL) {
printf("Stack is empty.\n");
return;
}
printf("Top element is %d\n", top->data);
}

// Function to display stack elements

void display() {
if (top == NULL) {
printf("Stack is empty.\n");
return;
}
struct Node* temp = top;
printf("Stack elements: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

// Main function
int main() {
int choice, value;

while (1) {
printf("\nStack using Linked List:\n");
printf("1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n");
printf("Enter your choice: ");
By Prof. Amogha A R
 scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter value to push: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
display();
break;
case 5:
printf("Exiting program.\n");
return 0;
default:
printf("Invalid choice! Try again.\n");
}
}
}

Example Output:

Stack using Linked List:

1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter value to push: 10
10 pushed to stack.

Enter your choice: 1

Enter value to push: 20
20 pushed to stack.

Enter your choice: 1

Enter value to push: 30
30 pushed to stack.

By Prof. Amogha A R
Enter your choice: 4
Stack elements: 30 20 10

Enter your choice: 3

Top element is 30

Enter your choice: 2

30 popped from stack.

Enter your choice: 4

Stack elements: 20 10

Enter your choice: 5

Exiting program.

By Prof. Amogha A R
11. Write a program to convert an infix expression x^y/(5*z)+2 to its postfix expression

Logic:
1. Infix Expression:
x^y / (5 * z) + 2
2. Operator Precedence & Associativity:
 ^ (Exponentiation) → Highest precedence, Right to Left
associativity.
 * and / (Multiplication & Division) → Medium precedence, Left to
Right associativity.
 + (Addition) → Lowest precedence, Left to Right associativity.
 Parentheses () → Override precedence.
3. Postfix Conversion Steps (Using Stack)
Convert x^y → xy^
Convert 5 * z → 5z*
Convert xy^ / (5 * z) → xy^5z*/
Convert xy^5z*/ + 2 → xy^5z*/2+
4. Final Postfix Expression:
xy^5z*/2+
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

// Stack structure
struct Stack {
int top;
char items[MAX];
};

// Function to initialize stack

void initStack(struct Stack *s) {
s->top = -1;
}
By Prof. Amogha A R
// Function to check if stack is empty
int isEmpty(struct Stack *s) {
return s->top == -1;
}

// Function to push an element onto stack

void push(struct Stack *s, char c) {
if (s->top == MAX - 1) {
printf("Stack Overflow!\n");
return;
}
s->items[++s->top] = c;
}

// Function to pop an element from stack

char pop(struct Stack *s) {
if (isEmpty(s)) {
return '\0';
}
return s->items[s->top--];
}

// Function to return top element of stack

char peek(struct Stack *s) {
if (isEmpty(s)) {
return '\0';
}
return s->items[s->top];
}

// Function to determine precedence of operators

int precedence(char op) {
if (op == '^') return 3; // Highest precedence, right associative
if (op == '*' || op == '/') return 2; // Medium precedence, left
associative
if (op == '+' || op == '-') return 1; // Lowest precedence, left
associative
return 0;
}

// Function to convert infix to postfix

void infixToPostfix(char *infix, char *postfix) {
struct Stack s;
initStack(&s);
int i, j = 0;

By Prof. Amogha A R
 for (i = 0; infix[i] != '\0'; i++) {
char ch = infix[i];

// If operand, add to postfix expression

if (isalnum(ch)) {
postfix[j++] = ch;
}
// If '(', push to stack
else if (ch == '(') {
push(&s, ch);
}
// If ')', pop until '(' is found
else if (ch == ')') {
while (!isEmpty(&s) && peek(&s) != '(') {
postfix[j++] = pop(&s);
}
pop(&s); // Remove '('
}
// If operator, process precedence
else {
while (!isEmpty(&s) && precedence(peek(&s)) >=
precedence(ch) && ch != '^') {
postfix[j++] = pop(&s);
}
push(&s, ch);
}
}

// Pop remaining operators from stack

while (!isEmpty(&s)) {
postfix[j++] = pop(&s);
}

postfix[j] = '\0'; // Null-terminate string

}

int main() {
char infix[] = "x^y/(5*z)+2";
char postfix[MAX];

infixToPostfix(infix, postfix);
printf("Postfix Expression: %s\n", postfix);

return 0;
}

By Prof. Amogha A R
By Prof. Amogha A R
12. Write a program to evaluate a postfix expression 5 3+8 2 - *.

Logic:
Postfix Expression Given:

53+82-*

Evaluation:

-53+→8
-82-→6
- 8 * 6 → 48

Final Answer: 48

Steps to Evaluate Postfix Expression Using Stack:

1. Scan the expression from left to right.

2. If the token is an operand (number), push it onto the stack.
3. If the token is an operator, pop two elements from the stack, apply the
operation, and push the result back onto the stack.
4. The final result will be at the top of the stack.

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

#define MAX 100

// Stack structure
struct Stack {
int top;
int items[MAX];
};

// Initialize stack
By Prof. Amogha A R
void initStack(struct Stack *s) {
s->top = -1;
}

// Check if stack is empty

int isEmpty(struct Stack *s) {
return s->top == -1;
}

// Push element onto stack

void push(struct Stack *s, int value) {
if (s->top == MAX - 1) {
printf("Stack Overflow!\n");
return;
}
s->items[++s->top] = value;
}

// Pop element from stack

int pop(struct Stack *s) {
if (isEmpty(s)) {
printf("Stack Underflow!\n");
return -1;
}
return s->items[s->top--];
}

// Function to evaluate postfix expression

int evaluatePostfix(char *expr) {
struct Stack s;
initStack(&s);
int i;

for (i = 0; expr[i] != '\0'; i++) {

char ch = expr[i];

// Ignore spaces
if (ch == ' ')
continue;

// If operand, push onto stack

if (isdigit(ch)) {
push(&s, ch - '0'); // Convert char to int
}
// If operator, pop two elements and perform operation
else {
int val2 = pop(&s);
By Prof. Amogha A R
 int val1 = pop(&s);
int result;

switch (ch) {
case '+': result = val1 + val2; break;
case '-': result = val1 - val2; break;
case '*': result = val1 * val2; break;
case '/': result = val1 / val2; break;
default:
printf("Invalid operator!\n");
return -1;
}

// Push result back onto stack

push(&s, result);
}
}

// Final result will be at the top of the stack

return pop(&s);
}

// Main function
int main() {
char postfix[] = "5 3 + 8 2 - *"; // Given postfix expression
int result = evaluatePostfix(postfix);

printf("Result: %d\n", result);

return 0;
}

By Prof. Amogha A R
13. Write a program to create a binary tree with the elements {18,15,40,50,30,17,41} after
creation insert 45 and 19 into tree and delete 15,17 and 41 from tree. Display the tree on
each insertion and deletion operation.

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

// Node structure for Binary Search Tree

struct Node {
int data;
struct Node *left, *right;
};

// Function to create a new node

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

By Prof. Amogha A R
// Function to insert a node in BST
struct Node* insert(struct Node* root, int value) {
if (root == NULL) return createNode(value);

if (value < root->data)

root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);

return root;
}

// Function to find the minimum node in right subtree (used for

deletion)
struct Node* minValueNode(struct Node* node) {
struct Node* current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}

// Function to delete a node in BST

struct Node* deleteNode(struct Node* root, int value) {
if (root == NULL) return root;

if (value < root->data)

root->left = deleteNode(root->left, value);
else if (value > root->data)
root->right = deleteNode(root->right, value);
else {
// Node with only one child or no child
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}

// Node with two children: Get the inorder successor (smallest

in right subtree)
struct Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
By Prof. Amogha A R
 }
return root;
}

// Function to perform inorder traversal (sorted order)

void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

// Main function
int main() {
struct Node* root = NULL;

// Initial BST creation

int elements[] = {18, 15, 40, 50, 30, 17, 41};
int n = sizeof(elements) / sizeof(elements[0]);

printf("Inserting elements: ");

for (int i = 0; i < n; i++) {
root = insert(root, elements[i]);
}
inorder(root);
printf("\n");

// Insert new elements

printf("\nInserting 45:\n");
root = insert(root, 45);
inorder(root);
printf("\n");

printf("\nInserting 19:\n");
root = insert(root, 19);
inorder(root);
printf("\n");

// Delete nodes
printf("\nDeleting 15:\n");
root = deleteNode(root, 15);
inorder(root);
printf("\n");

printf("\nDeleting 17:\n");
root = deleteNode(root, 17);
By Prof. Amogha A R
 inorder(root);
printf("\n");

printf("\nDeleting 41:\n");
root = deleteNode(root, 41);
inorder(root);
printf("\n");

return 0;
}

By Prof. Amogha A R
14. Write a program to create binary search tree with the elements {2,5,1,3,9,0,6} and
perform inorder, preorder and post order traversal.

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

// Define Node structure

struct Node {
int data;
struct Node *left, *right;
};

// Function to create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

By Prof. Amogha A R
 newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}

// Function to insert a node in BST

struct Node* insert(struct Node* root, int value) {
if (root == NULL) return createNode(value);

if (value < root->data)

root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);

return root;
}

// Function for Inorder Traversal (L -> Root -> R)

void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

// Function for Preorder Traversal (Root -> L -> R)

void preorder(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}

// Function for Postorder Traversal (L -> R -> Root)

void postorder(struct Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}

// Main Function
int main() {
struct Node* root = NULL;
By Prof. Amogha A R
 int elements[] = {2, 5, 1, 3, 9, 0, 6};
int n = sizeof(elements) / sizeof(elements[0]);

// Insert elements into BST

for (int i = 0; i < n; i++) {
root = insert(root, elements[i]);
}

// Perform Traversals
printf("Inorder Traversal: ");
inorder(root);
printf("\n");

printf("Preorder Traversal: ");

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

printf("Postorder Traversal: ");

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

return 0;
}

By Prof. Amogha A R
15. Write a program to Sort the following elements using heap sort {9.16,32,8,4,1,5,8,0}.

#include <stdio.h>

// Function to swap two numbers

void swap(float *a, float *b) {
float temp = *a;
*a = *b;
*b = temp;
}

// Function to heapify a subtree rooted at index i

void heapify(float arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child

// If left child is larger than root

By Prof. Amogha A R
 if (left < n && arr[left] > arr[largest])
largest = left;

// If right child is larger than largest so far

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

// If largest is not root

if (largest != i) {
swap(&arr[i], &arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}

// Function to perform Heap Sort

void heapSort(float arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// Extract elements from heap one by one

for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]); // Move current root to end
heapify(arr, i, 0); // Call max heapify on reduced heap
}
}

// Function to print an array

void printArray(float arr[], int n) {
for (int i = 0; i < n; i++)
printf("%.2f ", arr[i]);
printf("\n");
}

// Main function
int main() {
float arr[] = {9, 16, 32, 8, 4, 1, 5, 8, 0}; // Given elements
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

heapSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);
By Prof. Amogha A R
 return 0;
}

By Prof. Amogha A R
16. Given S1={“Flowers”} ; S2={“are beautiful”} I. Find the length of S1 II. Concatenate S1 and
S2 III. Extract the substring “low” from S1 IV. Find “are” in S2 and replace it with “is” .

#include <stdio.h>
#include <string.h>

int main() {
char S1[20] = "Flowers"; // Declaring S1
char S2[20] = "are beautiful"; // Declaring S2
char result[40]; // To store concatenated string
char substring[4]; // To store extracted substring

// I. Find the length of S1

int length = strlen(S1);
printf("Length of S1: %d\n", length);

By Prof. Amogha A R
 // II. Concatenate S1 and S2
strcpy(result, S1); // Copy S1 to result
strcat(result, " "); // Adding space between words
strcat(result, S2); // Append S2
printf("Concatenated String: %s\n", result);

// III. Extract substring "low" from S1

strncpy(substring, S1 + 1, 3); // Copy 3 characters from index 1
substring[3] = '\0'; // Null terminate
printf("Extracted substring: %s\n", substring);

// IV. Find "are" in S2 and replace with "is"

char modifiedS2[20];
strcpy(modifiedS2, S2);
char *pos = strstr(modifiedS2, "are");
if (pos != NULL) {
strncpy(pos, "is ", 3); // Replace "are" with "is "
}
printf("Modified S2: %s\n", modifiedS2);

return 0;
}

By Prof. Amogha A R
17. Write a program to implement adjacency matrix of a graph.

#include <stdio.h>

#define MAX 10 // Maximum number of vertices

// Function to display adjacency matrix

void displayMatrix(int matrix[MAX][MAX], int vertices) {
printf("\nAdjacency Matrix:\n");
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}

int main() {
int matrix[MAX][MAX] = {0}; // Initialize matrix with 0s
int vertices, edges, src, dest, isDirected;

// Get number of vertices and edges

printf("Enter the number of vertices: ");
scanf("%d", &vertices);
By Prof. Amogha A R
 printf("Enter the number of edges: ");
scanf("%d", &edges);

// Check if the graph is directed or undirected

printf("Enter 1 for Directed Graph, 0 for Undirected Graph: ");
scanf("%d", &isDirected);

// Take input for edges

printf("Enter edges (source destination):\n");
for (int i = 0; i < edges; i++) {
scanf("%d %d", &src, &dest);
matrix[src][dest] = 1; // Mark edge

if (!isDirected) {
matrix[dest][src] = 1; // For undirected graphs
}
}

// Display adjacency matrix

displayMatrix(matrix, vertices);

return 0;
}

By Prof. Amogha A R
By Prof. Amogha A R
18. Write a program to insert/retrieve an entry into hash/ from a hash table with open
addressing using linear probing.

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

#define TABLE_SIZE 10 // Define the hash table size

#define EMPTY -1 // Marker for empty slot

typedef struct {
int key;
int value;
} HashEntry;

HashEntry hashTable[TABLE_SIZE]; // Hash table

// Hash function
By Prof. Amogha A R
int hashFunction(int key) {
return key % TABLE_SIZE;
}

// Insert into hash table

void insert(int key, int value) {
int index = hashFunction(key);
int originalIndex = index;

// Linear probing
while (hashTable[index].key != EMPTY && hashTable[index].key !=
key) {
index = (index + 1) % TABLE_SIZE;
if (index == originalIndex) {
printf("Hash table is full!\n");
return;
}
}

hashTable[index].key = key;
hashTable[index].value = value;
printf("Inserted (%d, %d) at index %d\n", key, value, index);
}

// Retrieve from hash table

int search(int key) {
int index = hashFunction(key);
int originalIndex = index;

// Linear probing search

while (hashTable[index].key != EMPTY) {
if (hashTable[index].key == key) {
return hashTable[index].value;
}
index = (index + 1) % TABLE_SIZE;
if (index == originalIndex) {
break;
}
}
return -1; // Not found
}

// Initialize the hash table

void initializeTable() {
for (int i = 0; i < TABLE_SIZE; i++) {
hashTable[i].key = EMPTY;
hashTable[i].value = 0;
By Prof. Amogha A R
 }
}

// Display the hash table

void displayTable() {
printf("\nHash Table:\n");
for (int i = 0; i < TABLE_SIZE; i++) {
if (hashTable[i].key != EMPTY)
printf("Index %d: (%d, %d)\n", i, hashTable[i].key,
hashTable[i].value);
else
printf("Index %d: Empty\n", i);
}
}

int main() {
initializeTable();

insert(12, 100);
insert(22, 200);
insert(32, 300);
insert(42, 400);

displayTable();

// Searching for a key

int key = 22;
int value = search(key);
if (value != -1)
printf("\nValue for key %d: %d\n", key, value);
else
printf("\nKey %d not found!\n", key);

return 0;
}

By Prof. Amogha A R
Example Run
Output:
Inserted (12, 100) at index 2
Inserted (22, 200) at index 3
Inserted (32, 300) at index 4
Inserted (42, 400) at index 5

Hash Table:
Index 0: Empty
Index 1: Empty
Index 2: (12, 100)
Index 3: (22, 200)
Index 4: (32, 300)
Index 5: (42, 400)
Index 6: Empty
Index 7: Empty
Index 8: Empty
Index 9: Empty

Value for key 22: 200

By Prof. Amogha A R