Task 4: Construct a Queue ADT program that performs enqueue and dequeue operations
using arrays or linked lists
.AIM
To construct a Queue Abstract Data Type (ADT) and perform Enqueue and Dequeue
operations using array representation in C.
ALGORITHM
Enqueue Operation
1. Check if rear == MAX - 1
2. If true, display Queue Overflow
3. Else increment rear
4. Insert the element into queue[rear]
Dequeue Operation
1. Check if front > rear
2. If true, display Queue Underflow
3. Else remove the element at queue[front]
4. Increment front
C PROGRAM
#include <stdio.h>
#define MAX 5
int queue[MAX];
int front = 0, rear = -1;
void enqueue(int item) {
if (rear == MAX - 1) {
printf("Queue Overflow\n");
return;
}
queue[++rear] = item;
printf("%d inserted into queue\n", item);
}
void dequeue() {
if (front > rear) {
printf("Queue Underflow\n");
return;
}
printf("%d deleted from queue\n", queue[front++]);
}
void display() {
if (front > rear) {
printf("Queue is Empty\n");
return;
}
printf("Queue elements: ");
for (int i = front; i <= rear; i++)
printf("%d ", queue[i]);
printf("\n");
}
int main() {
int choice, item;
while (1) {
printf("\[Link] [Link] [Link] [Link]\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter element to insert: ");
scanf("%d", &item);
enqueue(item);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
return 0;
default:
printf("Invalid choice\n");
}
}
}
Task 5 Binary search Tree
Design, Develop and Implement the following tasks using Binary search Tree.
(i) Basic Operations of BST
(ii) Tree Traversal with Recursion
Task 5 (i): Basic Operations of BST
Aim
To design, develop, and implement a C program that performs the basic operations on a Binary
Search Tree (BST), including:
1. Insertion of a node
2. Deletion of a node
3. Searching for an element
4. Tree Traversals using recursion
o Inorder
o Preorder
o Postorder
Algorithm:
1. Start
2. Insertion
1. If the tree is empty, create a new node as root.
2. Otherwise, compare the new key with the root’s key:
If the new key < root → insert into left subtree.
If the new key > root → insert into right subtree.
3. Repeat recursively until the correct position is found.
3. Searching
1. Start from the root node.
2. If the key = root → element found.
3. If the key < root → search in left subtree.
4. If the key > root → search in right subtree.
5. If tree becomes NULL, element is not found.
4. Deletion
To delete a node with key = X:
1. Case 1: Node is a leaf → simply delete.
2. Case 2: Node has one child → replace node with child.
3. Case 3: Node has two children →
Find the inorder successor (smallest in right subtree).
Replace node’s data with successor’s data
Recursively delete the successor.
5. Traversals
Inorder (L → Root → R): Gives sorted order of nodes
Preorder (Root → L → R)
Postorder (L → R → Root)
6. Stop
#include <stdio.h>
#include <stdlib.h>
/* Definition of BST Node */
struct node {
int data;
struct node *left, *right;
};
/* 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;
}
/* Insert a node into 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;
}
/* Search an element in BST */
int search(struct node* root, int key) {
if (root == NULL)
return 0;
if (root->data == key)
return 1;
if (key < root->data)
return search(root->left, key);
else
return search(root->right, key);
}
/* Find minimum value node */
struct node* minValueNode(struct node* node) {
struct node* current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
/* Delete a node from BST */
struct node* deleteNode(struct node* root, int key) {
if (root == NULL)
return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
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;
}
struct node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
/* Inorder Traversal */
void inorder(struct node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
/* 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);
}
}
/* Main Function */
int main() {
struct node* root = NULL;
int choice, value;
while (1) {
printf("\n--- Binary Search Tree Operations ---\n");
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Search\n");
printf("4. Inorder Traversal\n");
printf("5. Preorder Traversal\n");
printf("6. Postorder Traversal\n");
printf("7. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
root = insert(root, value);
break;
case 2:
printf("Enter value to delete: ");
scanf("%d", &value);
root = deleteNode(root, value);
break;
case 3:
printf("Enter value to search: ");
scanf("%d", &value);
if (search(root, value))
printf("Element found in BST\n");
else
printf("Element not found in BST\n");
break;
case 4:
printf("Inorder Traversal: ");
inorder(root);
printf("\n");
break;
case 5:
printf("Preorder Traversal: ");
preorder(root);
printf("\n");
break;
case 6:
printf("Postorder Traversal: ");
postorder(root);
printf("\n");
break;
case 7:
return 0;
default:
printf("Invalid choice\n");
}
}
}
Sample Output
--- Binary Search Tree Operations ---
1. Insert
2. Delete
3. Search
4. Inorder Traversal
5. Preorder Traversal
6. Postorder Traversal
7. Exit
Enter value to insert: 50
Enter value to insert: 30
Enter value to insert: 70
Enter value to insert: 20
Enter value to insert: 40
Enter value to insert: 60
Enter value to insert: 80
Inorder Traversal:
20 30 40 50 60 70 80
Preorder Traversal:
50 30 20 40 70 60 80
Postorder Traversal:
20 40 30 60 80 70 50
Enter value to search: 40
Element found in BST
Enter value to delete: 30
Inorder Traversal:
20 40 50 60 70 80