Exercise 4
[Link] a program to implement Queue opera ons using linked list
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct Queue {
Node* front;
Node* rear;
} Queue;
Queue* createQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
q->front = q->rear = NULL;
return q;
void enqueue(Queue* q, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = newNode;
return;
q->rear->next = newNode;
q->rear = newNode;
}
int dequeue(Queue* q) {
if (q->front == NULL) {
prin ("Queue is empty.\n");
return -1;
Node* temp = q->front;
int data = temp->data;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
free(temp);
return data;
void display(Queue* q) {
if (q->front == NULL) {
prin ("Queue is empty.\n");
return;
Node* temp = q->front;
prin ("Queue: ");
while (temp != NULL) {
prin ("%d ", temp->data);
temp = temp->next;
prin ("\n");
}
int main() {
Queue* q = createQueue();
enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
display(q);
prin ("Dequeued: %d\n", dequeue(q));
display(q);
return 0;
Output
Queue: 10 20 30
Dequeued: 10
Queue: 20 30
[Link] a program to implement queue opera ons using arrays
#include <stdio.h>
#define MAX_SIZE 100
struct Queue {
int queue[MAX_SIZE];
int front;
int rear;
};
void ini alizeQueue(struct Queue *q) {
q->front = -1;
q->rear = -1;
}
int isEmpty(struct Queue *q) {
return (q->front == -1);
int isFull(struct Queue *q) {
return (q->rear == MAX_SIZE - 1);
void enqueue(struct Queue *q, int data) {
if (isFull(q)) {
prin ("Queue is full\n");
return;
if (isEmpty(q)) {
q->front = 0;
q->rear++;
q->queue[q->rear] = data;
prin ("Enqueued %d into the queue\n", data);
int dequeue(struct Queue *q) {
if (isEmpty(q)) {
prin ("Queue is empty\n");
return -1;
int data = q->queue[q->front];
if (q->front == q->rear) { // Reset when the last element is dequeued
q->front = -1;
q->rear = -1;
} else {
q->front++;
prin ("Dequeued element: %d\n", data);
return data;
void display(struct Queue *q)
if (isEmpty(q)) {
prin ("Queue is empty\n");
return;
for (int i = q->front; i <= q->rear; i++) {
prin ("%d ", q->queue[i]);
prin ("\n");
int main()
struct Queue q;
ini alizeQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
prin ("Elements in the queue: ");
display(&q);
dequeue(&q);
prin ("Elements in the queue a er dequeue: ");
display(&q);
return 0;
Output
Enqueued 10 into the queue
Enqueued 20 into the queue
Enqueued 30 into the queue
Elements in the queue: 10 20 30
Dequeued element: 10
Elements in the queue a er dequeue: 20 30
[Link] a program to implement circular queues using linked list
#include <stdio.h>
#include <stdlib.h>
struct Node
int data;
struct Node* next;
};
struct CircularQueue
struct Node* front;
struct Node* rear;
};
struct Node* createNode(int data)
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
struct CircularQueue* createQueue()
struct CircularQueue* queue = (struct CircularQueue*)malloc(sizeof(struct
CircularQueue));
queue->front = queue->rear = NULL;
return queue;
void enqueue(struct CircularQueue* queue, int data) {
struct Node* newNode = createNode(data);
if (queue->rear == NULL) {
queue->front = queue->rear = newNode;
queue->rear->next = queue->front; // Circular link
} else {
queue->rear->next = newNode;
queue->rear = newNode;
queue->rear->next = queue->front; // Maintain circular link
prin ("Enqueued: %d\n", data);
int dequeue(struct CircularQueue* queue) {
if (queue->front == NULL) {
prin ("Queue is empty!\n");
return -1;
int data;
if (queue->front == queue->rear) { // Single element case
data = queue->front->data;
free(queue->front);
queue->front = queue->rear = NULL;
} else {
struct Node* temp = queue->front;
data = temp->data;
queue->front = queue->front->next;
queue->rear->next = queue->front; // Maintain circular link
free(temp);
prin ("Dequeued: %d\n", data);
return data;
void displayQueue(struct CircularQueue* queue)
if (queue->front == NULL) {
prin ("Queue is empty!\n");
return;
struct Node* temp = queue->front;
prin ("Queue: ");
do {
prin ("%d ", temp->data);
temp = temp->next;
} while (temp != queue->front);
prin ("\n");
}
int main()
struct CircularQueue* queue = createQueue();
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
displayQueue(queue);
dequeue(queue);
displayQueue(queue);
enqueue(queue, 40);
displayQueue(queue);
return 0;
Output
Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue: 10 20 30
Dequeued: 10
Queue: 20 30
Enqueued: 40
Queue: 20 30 40
Exercise 5
[Link] a program to implement binary tree traversal using linked list
#include <stdio.h>
#include <stdlib.h>
struct Node
int data;
struct Node* le ;
struct Node* right;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->le = NULL;
newNode->right = NULL;
return newNode;
struct Node* insertNode(struct Node* root, int data) {
if (root == NULL) {
return createNode(data);
if (data < root->data) {
root->le = insertNode(root->le , data);
} else {
root->right = insertNode(root->right, data);
return root;
int searchNode(struct Node* root, int key) {
if (root == NULL) return 0; // Key not found
if (root->data == key) return 1; // Key found
if (key < root->data) return searchNode(root->le , key);
return searchNode(root->right, key);
struct Node* findMin(struct Node* root)
while (root->le != NULL) root = root->le ;
return root;
struct Node* deleteNode(struct Node* root, int key)
if (root == NULL) return root;
if (key < root->data) {
root->le = deleteNode(root->le , key);
} else if (key > root->data) {
root->right = deleteNode(root->right, key);
} else {
if (root->le == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->le ;
free(root);
return temp;
struct Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
void inOrderTraversal(struct Node* root) {
if (root != NULL) {
inOrderTraversal(root->le );
prin ("%d ", root->data);
inOrderTraversal(root->right);
int main() {
struct Node* root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 70);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 60);
insertNode(root, 80);
prin ("In-Order Traversal: ");
inOrderTraversal(root);
prin ("\nSearching for 40: %s\n", searchNode(root, 40) ? "Found" : "Not Found");
prin ("Dele ng 30...\n");
root = deleteNode(root, 30);
prin ("In-Order Traversal a er Dele on: ");
inOrderTraversal(root);
return 0;
Output
In-Order Traversal: 20 30 40 50 60 70 80
Searching for 40: Found
Dele ng 30...
In-Order Traversal a er Dele on: 20 40 50 60 70 80
2,Write a program to create binary search tree for given list of [Link] inorder
traversal of the tree .Implement inser on and dele on opera ons
#include <stdio.h>
#include <stdlib.h>
struct Node
int key;
struct Node *le , *right;
};
struct Node* newNode(int key) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->key = key;
temp->le = temp->right = NULL;
return temp;
struct Node* insert(struct Node* node, int key)
if (node == NULL) {
return newNode(key);
if (key < node->key) {
node->le = insert(node->le , key);
} else if (key > node->key) {
node->right = insert(node->right, key);
}
return node;
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->le );
prin ("%d ", root->key);
inorder(root->right);
struct Node* search(struct Node* root, int key) {
if (root == NULL || root->key == key) {
return root;
if (root->key < key) {
return search(root->right, key);
return search(root->le , key);
struct Node* minValueNode(struct Node* node) {
struct Node* current = node;
while (current && current->le != NULL) {
current = current->le ;
return current;
}
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL) {
return root;
if (key < root->key) {
root->le = deleteNode(root->le , key);
} else if (key > root->key) {
root->right = deleteNode(root->right, key);
} else {
if (root->le == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->le ;
free(root);
return temp;
struct Node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
return root;
}
int main() {
struct Node* root = NULL;
int choice, key;
while (1) {
prin ("\nBinary Search Tree Opera ons Menu:\n");
prin ("1. Insert\n");
prin ("2. Search\n");
prin ("3. Delete\n");
prin ("4. In-order Traversal\n");
prin ("5. Exit\n");
prin ("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
prin ("Enter the key to insert: ");
scanf("%d", &key);
root = insert(root, key);
break;
case 2:
prin ("Enter the key to search: ");
scanf("%d", &key);
struct Node* result = search(root, key);
if (result != NULL) {
prin ("Key %d found in the BST.\n", key);
} else {
prin ("Key %d not found in the BST.\n", key);
break;
case 3:
prin ("Enter the key to delete: ");
scanf("%d", &key);
root = deleteNode(root, key);
break;
case 4:
prin ("In-order Traversal of the BST: ");
inorder(root);
prin ("\n");
break;
case 5:
exit(0);
default:
prin ("Invalid choice! Please enter a valid op on.\n");
return 0; // Return 0 to indicate successful execu on
Output
Binary Search Tree Opera ons Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 1
Enter the key to insert: 23
Binary Search Tree Opera ons Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 1
Enter the key to insert: 34
Binary Search Tree Opera ons Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 1
Enter the key to insert: 45
Binary Search Tree Opera ons Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 2
Enter the key to search: 25
Key 25 not found in the BST.
Binary Search Tree Opera ons Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 4
In-order Traversal of the BST: 23 34 45
Binary Search Tree Opera ons Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 3
Enter the key to delete: 34
Binary Search Tree Opera ons Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 4
In-order Traversal of the BST: 23 45
Binary Search Tree Opera ons Menu:
1. Insert
2. Search
3. Delete
4. In-order Traversal
5. Exit
Enter your choice: 5