EXP.

NO : 7

IMPLEMENTATION OF LINKED LISTS

DATE :

AIM:
To write a C program to implement singly and doubly linked lists.

ALGORITHM:
Singly Linked List Algorithm:
Step 1: Start.
Step 2: Create a new node by allocating memory and initializing its data field with the
given data.
Step 3: Insert the new node at the beginning of the list by updating the head pointer.
Step 4: Insert the new node at the end of the list by traversing the list and updating the
next pointer of the last node.
Step 5: Delete a node from the list by updating the next pointer of the previous node to
skip over the node to be deleted.
Step 6: Display the list by traversing the list and printing the data of each node.
Step 7: End.
Doubly Linked List Algorithm:
Step 1: Start.
Step 2: Create a new node by allocating memory and initializing its data field with the
given data.
Step 3: Insert the new node at the beginning of the list by updating the head pointer and
setting the previous pointer of the new node to NULL.
Step 4: Insert the new node at the end of the list by traversing the list and updating the
next pointer of the last node, and setting the previous pointer of the new node to the last
node.
Step 5: Delete a node from the list by updating the next pointer of the previous node to
skip over the node to be deleted, and updating the previous pointer of the next node to
point to the previous node.
Step 6: Display the list by traversing the list and printing the data of each node, which
can be done in both forward and backward directions using the next and previous
pointers.
Step 7: End.

PROGRAM 1:
#include <stdio.h>
#include <stdlib.h>

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

// Create and return a new node

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

// Insert at a specific position (0 for beginning, -1 for end)

void insert(struct Node** head, int data, int position) {
struct Node* newNode = createNode(data);
if (position == 0 || *head == NULL) {
newNode->next = *head;
*head = newNode;
return;
}
struct Node* temp = *head;
int i = 1;
if (position == -1) {
while (temp->next) temp = temp->next;
} else {
while (temp->next && i < position) temp = temp->next, i++;
}
newNode->next = temp->next;
temp->next = newNode;
}

// Delete node at a specific position (0 for beginning, -1 for end)

void deleteNode(struct Node** head, int position) {
if (*head == NULL) return;
struct Node* temp = *head;
if (position == 0) {
*head = temp->next;
free(temp);
return;
}
int i = 1;
struct Node* prev = NULL;
if (position == -1) {
while (temp->next) prev = temp, temp = temp->next;
} else {
while (temp->next && i < position) prev = temp, temp = temp->next, i++;
}
if (prev) prev->next = temp->next;
free(temp);
}
// Print the linked list
void printList(struct Node* head) {
while (head) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}

int main() {
struct Node* head = NULL;
int choice, data, pos;

while (1) {
printf("Singly Linked List");
printf("\n1. Insert\n2. Delete\n3. Print\n4. Exit\nEnter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter data: ");
scanf("%d", &data);
printf("Enter position (0 for beginning, -1 for end , or specific index position): ");
scanf("%d", &pos);
insert(&head, data, pos);
break;
case 2:
printf("Enter position to delete (0 for beginning, -1 for end, or specific index position):
");
OUTPUT:
scanf("%d", &pos);
deleteNode(&head, pos);
break;
case 3:
printList(head);
break;
case 4:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
}

PROGRAM 2 :
#include <stdio.h>
#include <stdlib.h>

// Node structure for doubly linked list

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

// Create and return a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Insert at a specific position (0 for beginning, -1 for end, any other value for middle)
void insert(struct Node** head, int data, int position) {
struct Node* newNode = createNode(data);
if (*head == NULL || position == 0) { // Insert at beginning
if (*head != NULL) (*head)->prev = newNode;
newNode->next = *head;
*head = newNode;
return;
}
struct Node* temp = *head;
int i = 1;
if (position == -1) { // Insert at the end
while (temp->next) temp = temp->next;
} else { // Insert at a specific middle position
while (temp->next && i < position) temp = temp->next, i++;
}
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next) temp->next->prev = newNode;
temp->next = newNode;
}

// Delete node at a specific position (0 for beginning, -1 for end, any other value for middle)
void deleteNode(struct Node** head, int position) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
if (position == 0) { // Delete from beginning
*head = temp->next;
if (*head) (*head)->prev = NULL;
free(temp);
return;
}
int i = 1;
if (position == -1) { // Delete from the end
while (temp->next) temp = temp->next;
} else { // Delete from a specific middle position
while (temp->next && i < position) temp = temp->next, i++;
}
if (temp->prev) temp->prev->next = temp->next;
if (temp->next) temp->next->prev = temp->prev;
free(temp);
}

// Print the list forward

void printListForward(struct Node* head) {
while (head) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// Print the list backward
void printListBackward(struct Node* head) {
if (head == NULL) return;
while (head->next) head = head->next;
while (head) {
printf("%d -> ", head->data);
head = head->prev;
}
printf("NULL\n");
}

int main() {
struct Node* head = NULL;
int choice, data, pos;

while (1) {
printf("\n Doubly Linked List\n1. Insert\n2. Delete\n3. Print Forward\n4. Print Backward\n5.
Exit\nEnter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter data: ");
scanf("%d", &data);
printf("Enter position (0 for beginning, -1 for end, or specific position): ");
scanf("%d", &pos);
insert(&head, data, pos);
break;
case 2:
printf("Enter position to delete (0 for beginning, -1 for end, or specific position): ");
scanf("%d", &pos);
deleteNode(&head, pos);
break;
case 3:
printListForward(head);
break;
case 4:
printListBackward(head);
break;
case 5:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
}

RESULT :
Thus the C program to implement singly and doubly linked lists was successfully
executed and verified.
EXP.NO : 8
IMPLEMENTATION PRIORITY QUEUE
DATE :

AIM :
To write a C program to implement Priority Queue.

ALGORITHM :
Step 1 ; Start.
Step 2: Create an empty priority queue.
Step 3: Enqueue: Create a new node with the given element and priority, and insert it
into the queue in the correct position based on its priority.
Step 4: Dequeue: Remove the node with the highest priority from the queue, update the
head of the queue to point to the next node, and return the removed node's element.
Step 5: Peek: Return the element of the node with the highest priority without removing it
from the queue.
Step 6: Display: Traverse the queue and print the elements in the order of their priority,
along with their priority.
Step 7: End.
OUTPUT :
PROGRAM :
#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node in the priority queue

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

// Define the structure for the priority queue

typedef struct PriorityQueue {
Node* front;
Node* rear;
} PriorityQueue;

// Function to create a new node

Node* createNode(int data, int priority) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory error\n");
return NULL;
}
newNode->data = data;
newNode->priority = priority;
newNode->next = NULL;
return newNode;
}
// Function to create a new priority queue
PriorityQueue* createPriorityQueue() {
PriorityQueue* queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));
if (!queue) {
printf("Memory error\n");
return NULL;
}
queue->front = NULL;
queue->rear = NULL;
return queue;
}

// Function to enqueue an element into the priority queue

void enqueue(PriorityQueue* queue, int data, int priority) {
Node* newNode = createNode(data, priority);
if (queue->rear == NULL) {
queue->front = newNode;
queue->rear = newNode;
} else {
if (priority > queue->rear->priority) {
newNode->next = queue->rear;
queue->rear = newNode;
} else {
Node* current = queue->front;
while (current->next != NULL && current->next->priority >= priority) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
}

// Function to dequeue an element from the priority queue

int dequeue(PriorityQueue* queue) {
if (queue->front == NULL) {
printf("Queue is empty\n");
return -1;
}
int data = queue->front->data;
Node* temp = queue->front;
queue->front = queue->front->next;
if (queue->front == NULL) {
queue->rear = NULL;
}
free(temp);
return data;
}

// Function to peek at the front element of the priority queue

int peek(PriorityQueue* queue) {
if (queue->front == NULL) {
printf("Queue is empty\n");
return -1;
}
return queue->front->data;
}

// Function to display the elements of the priority queue

void display(PriorityQueue* queue) {
Node* current = queue->front;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}

int main() {
PriorityQueue* queue = createPriorityQueue();
int choice, data, priority;
while (1) {
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Peek\n");
printf("4. Display\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data: ");
scanf("%d", &data);
printf("Enter priority: ");
scanf("%d", &priority);
enqueue(queue, data, priority);
break;
case 2:
printf("Dequeued element: %d\n", dequeue(queue));
break;
case 3:
printf("Front element: %d\n", peek(queue));
break;
case 4:
display(queue);
break;
case 5:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
}

RESULT :
Thus the C program to implement Priority Queue was successfully executed and
verified.
EXP.NO : 9
IMPLEMENTATION OF BINARY TREE
DATE :

AIM :
To write a C program to implement Binary Tree.

ALGORITHM :
Step 1 : Start.
Step 2: Start by checking if the tree is empty for relevant operations (e.g., traversal, find
min/max). If yes, output that the tree is empty.
Step 3: To insert a node, traverse from the root:
o If NULL, create a new node.

o Move left if data is less; move right if data is greater. Repeat until insertion point
is found.
Step 4: To delete a node, find the node:
o If data matches:

 No children: delete node.

 One child: replace node with its child.
 Two children: replace with in-order successor (min value in right subtree)
and delete successor.
o Return modified tree.

Step 5: For inorder traversal (left-root-right), preorder traversal (root-left-right), or

postorder traversal (left-right-root), recursively visit nodes in the defined order.
Step 6: To find min, traverse to the leftmost node; for find max, traverse to the rightmost
node. Return the data of the found node.
Step 7: Display menu for user actions (insert, delete, traversals, find min/max, exit), get
user input, and execute the chosen operation.
Step 8: Handle invalid input with an error message and repeat until the user exits.
Step 9 : End.
OUTPUT :
PROGRAM :
#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node in the binary tree

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

// Function to create a new node

Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory error\n");
return NULL;
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Function to insert a node into the binary tree

Node* insertNode(Node* root, int data) {
if (root == NULL) {
root = createNode(data);
} else if (data < root->data) {
root->left = insertNode(root->left, data);
} else if (data > root->data) {
root->right = insertNode(root->right, data);
}
return root;
}

// Function to delete a node from the binary tree

Node* deleteNode(Node* root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
Node* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}

// Function to find the minimum value in the binary tree

int findMin(Node* root) {
if (root == NULL) {
printf("The tree is empty\n");
return -1; // Return an error value or use a different convention as needed
}
Node* current = root;
while (current->left != NULL) {
current = current->left;
}
return current->data;
}

// Function to find the maximum value in the binary tree

int findMax(Node* root) {
if (root == NULL) {
printf("The tree is empty\n");
return -1; // Return an error value or use a different convention as needed
}
Node* current = root;
while (current->right != NULL) {
current = current->right;
}
return current->data;
}
// Function to perform inorder traversal of the binary tree
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}

// Function to perform preorder traversal of the binary tree

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

// Function to perform postorder traversal of the binary tree

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

int main() {
Node* root = NULL;
int choice, data;
while (1) {
printf(“Binary Tree\n”);
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Inorder Traversal\n");
printf("4. Preorder Traversal\n");
printf("5. Postorder Traversal\n");
printf("6. Find Min\n");
printf("7. Find Max\n");
printf("8. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data: ");
scanf("%d", &data);
root = insertNode(root, data);
break;
case 2:
printf("Enter data: ");
scanf("%d", &data);
root = deleteNode(root, data);
break;
case 3:
inorderTraversal(root);
printf("\n");
break;
case 4:
preorderTraversal(root);
printf("\n");
break;
case 5:
postorderTraversal(root);
printf("\n");
break;
case 6:
printf("Minimum value: %d\n", findMin(root));
break;
case 7:
printf("Maximum value: %d\n", findMax(root));
break;
case 8:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
}

RESULT :
Thus the C program for Binary Tree was successfully executed and verified.
EXP.NO : 10

IMPLEMENTATION OF BINARY SEARCH TREE

DATE :

AIM :
To write a C program to implement Binary Search Tree.

ALGORITHM :
Step 1: Start .
Step 2: Take user input for the menu choice.
Step 3: Based on the user's choice, perform the corresponding operation:
 Insert a node:
o Check if the tree is empty (root == NULL). If true, create a new node as the root.

o Traverse the tree starting from the root:

 Move left if the data is less than the current node’s data.
 Move right if the data is greater than the current node’s data.
 Insert the new node at the found position.
 Delete a node:
o Find the node to be deleted by comparing data:

 Move left or right based on comparisons.

o If the node is found:

 If it has no children, delete it.

 If it has one child, replace it with its child and free the node.
 If it has two children, find the in-order successor (smallest value in the
right subtree), replace the node's data with it, and delete the successor.
 Inorder traversal (left-root-right):
o Recursively visit the left subtree, print the node’s data, then visit the right subtree.

 Preorder traversal (root-left-right):

o Print the node’s data, recursively visit the left subtree, then the right subtree.
OUTPUT :
 Postorder traversal (left-right-root):
o Recursively visit the left subtree, then the right subtree, and print the node’s data.

 Find the minimum value:

o Traverse to the leftmost node and return its data.

 Find the maximum value:

o Traverse to the rightmost node and return its data.

Step 4: Print the result of the operation (e.g., node data for traversal, min/max value).
Step 5: Repeat the process until the user selects the option to exit.
Step 6: If the user inputs an invalid choice, display an error message and prompt for input
again.
Step 7: End.

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

// Define the structure for a node in the binary search tree

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

// Function to create a new node

Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory error\n");
return NULL;
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Function to insert a node into the binary search tree

Node* insertNode(Node* root, int data) {
if (root == NULL) {
root = createNode(data);
} else if (data < root->data) {
root->left = insertNode(root->left, data);
} else if (data > root->data) {
root->right = insertNode(root->right, data);
}
return root;
}

// Function to delete a node from the binary search tree

Node* deleteNode(Node* root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
Node* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}

// Function to perform inorder traversal of the binary search tree

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

// Function to perform preorder traversal of the binary search tree

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

// Function to perform postorder traversal of the binary search tree

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

// Function to find the minimum value in the binary search tree

int findMin(Node* root) {
if (root == NULL) {
return -1;
}
while (root->left != NULL) {
root = root->left;
}
return root->data;
}

// Function to find the maximum value in the binary search tree

int findMax(Node* root) {
if (root == NULL) {
return -1;
}
while (root->right != NULL) {
root = root->right;
}
return root->data;
}

int main() {
Node* root = NULL;
int choice, data;
while (1) {
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Inorder Traversal\n");
printf("4. Preorder Traversal\n");
printf("5. Postorder Traversal\n");
printf("6. Find Min\n");
printf("7. Find Max\n");
printf("8. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data: ");
scanf("%d", &data);
root = insertNode(root, data);
break;
case 2:
printf("Enter data: ");
scanf("%d", &data);
root = deleteNode(root, data);
break;
case 3:
inorderTraversal(root);
printf("\n");
break;
case 4:
preorderTraversal(root);
printf("\n");
break;
case 5:
postorderTraversal(root);
printf("\n");
break;
case 6:
printf("Min value: %d\n", findMin(root));
break;
case 7:
printf("Max value: %d\n", findMax(root));
break;
case 8:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
}

RESULT :
Thus the C program for Binary Search Tree was successfully executed and verified.