Q1.

Write a program in C to accepts two polynomials as input and

prints the resultant polynomial due to the multiplication of input
polynomials. (5 marks)

Here’s a C program that accepts two polynomials as input and prints the resultant polynomial due to the
multiplication of the input polynomials.

Explanation:
In this program:
 We represent each polynomial as an array where the index represents the power of the variable (x) and
the value at each index represents the coefficient of that power.
We perform polynomial multiplication by multiplying each term of the first polynomial by every term
of the second polynomial and store the results in the resulting polynomial array.

Code:
#include <stdio.h> language-c

// Function to multiply two polynomials

void multiplyPolynomials(int poly1[], int poly2[], int poly1Degree, int poly2Degree, int
result[]) {
// Initialize the result polynomial array with zeros
for (int i = 0; i <= poly1Degree + poly2Degree; i++) {
result[i] = 0;
}

// Multiply each term of poly1 with every term of poly2

for (int i = 0; i <= poly1Degree; i++) {
for (int j = 0; j <= poly2Degree; j++) {
result[i + j] += poly1[i] * poly2[j];
}
}
}

// Function to print a polynomial

void printPolynomial(int poly[], int degree) {
for (int i = degree; i >= 0; i--) {
if (poly[i] != 0) {
if (i != degree && poly[i] > 0) {
printf(" + ");
}
if (i == 0 || poly[i] != 1) {
printf("%d", poly[i]);
}
if (i > 0) {
printf("x");
if (i > 1) {
printf("^%d", i);
}
}
}
}
printf("\n");
}

int main() {
int poly1Degree, poly2Degree;

// Input degree of the first polynomial

printf("Enter the degree of the first polynomial: ");
scanf("%d", &poly1Degree);

int poly1[poly1Degree + 1];

// Input coefficients of the first polynomial
 printf("Enter the coefficients of the first polynomial (from degree 0 to %d):\n",
poly1Degree);
for (int i = 0; i <= poly1Degree; i++) {
printf("Coefficient of x^%d: ", i);
scanf("%d", &poly1[i]);
}

// Input degree of the second polynomial

printf("Enter the degree of the second polynomial: ");
scanf("%d", &poly2Degree);

int poly2[poly2Degree + 1];

// Input coefficients of the second polynomial
printf("Enter the coefficients of the second polynomial (from degree 0 to %d):\n",
poly2Degree);
for (int i = 0; i <= poly2Degree; i++) {
printf("Coefficient of x^%d: ", i);
scanf("%d", &poly2[i]);
}

// Resultant polynomial degree will be sum of degrees of both polynomials

int resultDegree = poly1Degree + poly2Degree;
int result[resultDegree + 1];

// Multiply the polynomials

multiplyPolynomials(poly1, poly2, poly1Degree, poly2Degree, result);

// Print the result

printf("Resultant polynomial after multiplication: ");
printPolynomial(result, resultDegree);

return 0;
}

How the Program Works:

1. Input:
The user is asked to enter the degree of the first and second polynomials.
After that, the coefficients of each polynomial are provided by the user.
2. Multiplication Logic:
We iterate through both polynomials and multiply the corresponding terms (coefficients).
The degree of the resulting term is the sum of the degrees of the terms being multiplied.
3. Result:
The resultant polynomial is stored and printed.

Example Input and Output:

Input:
Enter the degree of the first polynomial: 2
Enter the coefficients of the first polynomial (from degree 0 to 2):
Coefficient of x^0: 1
Coefficient of x^1: 2
Coefficient of x^2: 1
Enter the degree of the second polynomial: 1
Enter the coefficients of the second polynomial (from degree 0 to 1):
Coefficient of x^0: 1
Coefficient of x^1: 3

Output:
Resultant polynomial after multiplication: x^3 + 5x^2 + 5x + 1

Explanation of the Output:

The first polynomial is (x^2 + 2x + 1).
The second polynomial is (3x + 1).
The resultant polynomial after multiplying the two is (x^3 + 5x^2 + 5x + 1).

Q2. Write a program in ‘C’ to create a single linked list and perform the
following operations on it:

- (i) Insert a new node at the beginning, in the middle or at the end of the
linked list.

- (ii) Delete a node from the linked list

- (iii) Display the linked list in reverse order

- (iv) Sort and display data of the linked list in ascending order.

- (v) Count the number of items stored in a single linked list

Here is a complete C program to create a singly linked list and perform the specified operations:

#include <stdio.h> language-c

#include <stdlib.h>

// Define the structure for a node in the linked list

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

// Function to create 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;
}

// Function to insert a node at the beginning

void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}

// Function to insert a node at the end

void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}

// (i) Insert a new node at the beginning, in the middle or at the end of the linked list.
Function to insert a node in the middle
void insertInMiddle(struct Node** head, int data, int position) {
struct Node* newNode = createNode(data);
if (position == 1) {
insertAtBeginning(head, data);
return;
}
struct Node* temp = *head;
for (int i = 1; i < position - 1 && temp != NULL; i++)
temp = temp->next;
if (temp == NULL) {
printf("Position out of range\n");
return;
}
newNode->next = temp->next;
temp->next = newNode;
}

// (ii) Delete a node from the linked list. Function to delete a node
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* prev = NULL;

if (temp != NULL && temp->data == key) {

*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("Node with value %d not found\n", key);
return;
}
 prev->next = temp->next;
free(temp);
}

// (iii) Display the linked list in reverse order. Function to reverse the linked list
recursively
void displayReverse(struct Node* head) {
if (head == NULL)
return;
displayReverse(head->next);
printf("%d -> ", head->data);
}

// Function to display the linked list

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

// (iv) Sort and display data of the linked list in ascending order. Function to sort the
linked list
void sortList(struct Node** head) {
struct Node* current = *head;
struct Node* index = NULL;
int temp;

if (head == NULL)
return;

while (current != NULL) {

index = current->next;
while (index != NULL) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}

// (v) Function to Count the number of items stored in a single linked list
int countNodes(struct Node* head) {
int count = 0;
struct Node* temp = head;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}

// Main function to demonstrate the operations

int main() {
struct Node* head = NULL;
int choice, value, position;

do {
printf("\n\nMenu:\n");
printf("1. Insert at Beginning\n");
printf("2. Insert at End\n");
printf("3. Insert in Middle\n");
printf("4. Delete a Node\n");
printf("5. Display in Reverse\n");
printf("6. Sort List\n");
printf("7. Count Nodes\n");
printf("8. Display List\n");
printf("9. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter value to insert at beginning: ");
scanf("%d", &value);
insertAtBeginning(&head, value);
break;

case 2:
printf("Enter value to insert at end: ");
scanf("%d", &value);
insertAtEnd(&head, value);
break;

case 3:
printf("Enter value to insert: ");
scanf("%d", &value);
printf("Enter position to insert: ");
scanf("%d", &position);
insertInMiddle(&head, value, position);
break;

case 4:
printf("Enter value to delete: ");
scanf("%d", &value);
deleteNode(&head, value);
break;

case 5:
printf("Linked List in reverse order: ");
displayReverse(head);
printf("NULL\n");
break;

case 6:
sortList(&head);
 printf("Sorted list: ");
displayList(head);
break;

case 7:
printf("Number of nodes in the list: %d\n", countNodes(head));
break;

case 8:
printf("Linked List: ");
displayList(head);
break;

case 9:
printf("Exiting...\n");
break;

default:
printf("Invalid choice!\n");
}
} while (choice != 9);

return 0;
}

Explanation of Operations:
1. Insertion of Node:
You can insert a node at the beginning, middle, or end using options 1, 2, and 3.
2. Deletion of Node:
Deletes a node with a specified value from the linked list (option 4).
3. Display Reverse:
Recursively displays the linked list in reverse order (option 5).
4. Sorting:
Sorts the list in ascending order and displays it (option 6).
5. Counting Nodes:
Counts and prints the number of nodes present in the list (option 7).
6. Display List:
Displays the linked list in regular order (option 8).

Sample Input/Output:
Menu:
1. Insert at Beginning
2. Insert at End
3. Insert in Middle
4. Delete a Node
5. Display in Reverse
6. Sort List
7. Count Nodes
8. Display List
9. Exit
Enter your choice: 1
Enter value to insert at beginning: 10

Menu:
1. Insert at Beginning
2. Insert at End
3. Insert in Middle
4. Delete a Node
5. Display in Reverse
6. Sort List
7. Count Nodes
8. Display List
9. Exit
Enter your choice: 8
Linked List: 10 -> NULL

Q3. Write a program in ‘C’ to create a doubly linked list to store

integer values and perform the following operations on it:

- (i) Insert a new node at the beginning, in the middle or at the end of the
linked list.

- (ii) Delete a node from the linked list

- (iii) Sort and display data of the doubly linked list in ascending order.

- (iv) Count the number of items stored in a single linked list

- (v) Calculate the sum of all even integer numbers, stored in the doubly
linked list.

Here is a C program to create a doubly linked list to store integer values and perform the specified
operations:

#include <stdio.h> language-c

#include <stdlib.h>

// Define structure for a doubly linked list node

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

// Function to create 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;
}

// Function to insert a node at the beginning

void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
}

// Function to insert a node at the end

void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}

// Function to insert a node in the middle

void insertInMiddle(struct Node** head, int data, int position) {
struct Node* newNode = createNode(data);
if (position == 1) {
insertAtBeginning(head, data);
return;
}
struct Node* temp = *head;
for (int i = 1; i < position - 1 && temp != NULL; i++)
temp = temp->next;
if (temp == NULL) {
printf("Position out of range\n");
return;
}
newNode->next = temp->next;
if (temp->next != NULL)
temp->next->prev = newNode;
temp->next = newNode;
newNode->prev = temp;
}

// Function to delete a node

void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;

while (temp != NULL && temp->data != key) {

temp = temp->next;
 }
if (temp == NULL) {
printf("Node with value %d not found\n", key);
return;
}

if (temp->prev != NULL) {
temp->prev->next = temp->next;
} else {
*head = temp->next;
}

if (temp->next != NULL) {
temp->next->prev = temp->prev;
}

free(temp);
}

// Function to sort the doubly linked list

void sortList(struct Node** head) {
struct Node* current = *head;
struct Node* index = NULL;
int temp;

if (*head == NULL)
return;

while (current != NULL) {

index = current->next;
while (index != NULL) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}

// Function to count the number of nodes

int countNodes(struct Node* head) {
int count = 0;
struct Node* temp = head;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}

// Function to calculate the sum of all even numbers

int sumEvenNumbers(struct Node* head) {
int sum = 0;
 struct Node* temp = head;
while (temp != NULL) {
if (temp->data % 2 == 0) {
sum += temp->data;
}
temp = temp->next;
}
return sum;
}

// Function to display the doubly linked list

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

// Main function to demonstrate the operations

int main() {
struct Node* head = NULL;
int choice, value, position;

do {
printf("\n\nMenu:\n");
printf("1. Insert at Beginning\n");
printf("2. Insert at End\n");
printf("3. Insert in Middle\n");
printf("4. Delete a Node\n");
printf("5. Sort List\n");
printf("6. Count Nodes\n");
printf("7. Sum of Even Numbers\n");
printf("8. Display List\n");
printf("9. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter value to insert at beginning: ");
scanf("%d", &value);
insertAtBeginning(&head, value);
break;

case 2:
printf("Enter value to insert at end: ");
scanf("%d", &value);
insertAtEnd(&head, value);
break;

case 3:
printf("Enter value to insert: ");
scanf("%d", &value);
printf("Enter position to insert: ");
 scanf("%d", &position);
insertInMiddle(&head, value, position);
break;

case 4:
printf("Enter value to delete: ");
scanf("%d", &value);
deleteNode(&head, value);
break;

case 5:
sortList(&head);
printf("Sorted list: ");
displayList(head);
break;

case 6:
printf("Number of nodes in the list: %d\n", countNodes(head));
break;

case 7:
printf("Sum of even numbers: %d\n", sumEvenNumbers(head));
break;

case 8:
printf("Doubly Linked List: ");
displayList(head);
break;

case 9:
printf("Exiting...\n");
break;

default:
printf("Invalid choice!\n");
}
} while (choice != 9);

return 0;
}

Explanation of Operations:
1. Insertion of Node:
Inserts a node at the beginning, middle, or end using options 1, 2, and 3.
2. Deletion of Node:
Deletes a node with a specified value from the doubly linked list (option 4).
3. Sorting:
Sorts the list in ascending order and displays it (option 5).
4. Counting Nodes:
Counts and prints the number of nodes present in the doubly linked list (option 6).
5. Sum of Even Numbers:
Calculates and prints the sum of all even integer numbers stored in the list (option 7).
 6. Display List:
Displays the doubly linked list in forward order (option 8).

Sample Input/Output:
Menu:
1. Insert at Beginning
2. Insert at End
3. Insert in Middle
4. Delete a Node
5. Sort List
6. Count Nodes
7. Sum of Even Numbers
8. Display List
9. Exit
Enter your choice: 1
Enter value to insert at beginning: 15

Menu:
1. Insert at Beginning
2. Insert at End
3. Insert in Middle
4. Delete a Node
5. Sort List
6. Count Nodes
7. Sum of Even Numbers
8. Display List
9. Exit
Enter your choice: 8
Doubly Linked List: 15 <-> NULL

Q4. What is a Dequeue? Write algorithm to perform insert and delete

operations in a Dequeue.

A Dequeue (short for Double-Ended Queue) is a data structure that allows insertion and deletion of
elements from both ends — front and rear. Unlike regular queues where insertion happens at the rear and
deletion happens at the front, a dequeue provides more flexibility by supporting the following operations:

1. Insertion at the front (insertFront).

2. Insertion at the rear (insertRear).
3. Deletion from the front (deleteFront).
4. Deletion from the rear (deleteRear).

Dequeue can be implemented using arrays or linked lists.

Types of Dequeues:
1. Input-Restricted Dequeue: Allows insertion only at one end but deletion at both ends.
 2. Output-Restricted Dequeue: Allows deletion only from one end but insertion at both ends.

Operations on a Dequeue
1. insertFront(): Insert an element at the front of the dequeue.
2. insertRear(): Insert an element at the rear of the dequeue.
3. deleteFront(): Delete an element from the front of the dequeue.
4. deleteRear(): Delete an element from the rear of the dequeue.
5. isFull(): Check if the dequeue is full.
6. isEmpty(): Check if the dequeue is empty.

Algorithm for Insertion and Deletion Operations in a Dequeue

1. Algorithm for insertFront operation:

Algorithm insertFront(dequeue, element) language-text

1. If the dequeue is full (check using isFull function):

Display "Dequeue is full, cannot insert element at the front."
Return
2. If the dequeue is empty (check using isEmpty function):
Set both front and rear to 0
3. Else, if the front is at the first position (front == 0):
Set front to the last position (front = size - 1)
4. Else:
Decrement front by 1
5. Insert the element at front
6. Return

2. Algorithm for insertRear operation:

Algorithm insertRear(dequeue, element) language-text

1. If the dequeue is full (check using isFull function):

Display "Dequeue is full, cannot insert element at the rear."
Return
2. If the dequeue is empty (check using isEmpty function):
Set both front and rear to 0
3. Else, if rear is at the last position (rear == size - 1):
Set rear to 0
4. Else:
Increment rear by 1
5. Insert the element at rear
6. Return

3. Algorithm for deleteFront operation:

Algorithm deleteFront(dequeue) language-text

1. If the dequeue is empty (check using isEmpty function):

Display "Dequeue is empty, cannot delete from the front."
Return
2. Store the element at front in a variable (say temp)
3. If front is equal to rear (only one element in the dequeue):
Set both front and rear to -1 (dequeue becomes empty)
4. Else, if front is at the last position (front == size - 1):
Set front to 0
5. Else:
Increment front by 1
6. Return the stored element

4. Algorithm for deleteRear operation:

Algorithm deleteRear(dequeue) language-text

1. If the dequeue is empty (check using isEmpty function):

Display "Dequeue is empty, cannot delete from the rear."
Return
2. Store the element at rear in a variable (say temp)
3. If front is equal to rear (only one element in the dequeue):
Set both front and rear to -1 (dequeue becomes empty)
4. Else, if rear is at the first position (rear == 0):
Set rear to the last position (rear = size - 1)
5. Else:
Decrement rear by 1
6. Return the stored element

Example (Array-based Dequeue Implementation)

Let’s assume a dequeue of size 5. Initially, front and rear are set to -1 (indicating an empty queue).

1. Inserting an element at the front ( insertFront ):

If the dequeue is empty, both front and rear are set to 0.
If the front is at position 0, it is moved to the last position ( size - 1 ).
2. Inserting an element at the rear ( insertRear ):
If the dequeue is empty, both front and rear are set to 0.
If rear is at the last position ( size - 1 ), it wraps around to 0.
3. Deleting an element from the front ( deleteFront ):
If the dequeue has only one element ( front == rear ), both are reset to -1 .
Otherwise, the front pointer is incremented (or wraps around if it was at the last position).
4. Deleting an element from the rear ( deleteRear ):
If the dequeue has only one element ( front == rear ), both are reset to -1 .
Otherwise, the rear pointer is decremented (or wraps around if it was at the first position).

Q5. Draw the binary tree for which the traversal sequences are given
as follows:

- (i) Pre order: A B D E F C G H I J K

In order: B E D F A C I H K J G

- (ii) Post order: I J H D K E C L M G F B A

In order: I H J D C K E A F L G M B
Understanding the Problem:
To solve the problem of drawing a binary tree from traversal sequences, it's essential to know the properties
of different traversal methods:

Pre-order traversal (Root, Left, Right): Visits the root node first, followed by the left subtree, and
then the right subtree.
In-order traversal (Left, Root, Right): Visits the left subtree first, then the root node, and then the
right subtree.
Post-order traversal (Left, Right, Root): Visits the left subtree first, followed by the right subtree,
and finally the root node.

By using both pre-order and in-order (or post-order and in-order) sequences, we can uniquely
reconstruct the binary tree.

(i)
Given:

Pre-order: A B D E F C G H I J K
In-order: B E D F A C I H K J G

Steps to Build the Binary Tree:

1. Pre-order tells us the root node. The first element is always the root.
Root: A
2. In in-order, locate the position of A . Elements to the left of A in the in-order sequence are in the
left subtree, and elements to the right are in the right subtree.
In-order (Left Subtree): B E D F
In-order (Right Subtree): C I H K J G
3. Continue recursively using the pre-order sequence for the left and right subtrees.

Constructing the Tree:

From the pre-order sequence, the next element after A is B , which becomes the root of the left
subtree.
In the in-order sequence, B has no left child.
The next element in pre-order after B is D , which is the right child of B .
Continue this process to construct the entire tree.

Binary Tree for (i):

A
/ \
B C
\ \
D G
/ \ / \
E F H J
\ \
I K
(ii)
Given:

Post-order: I J H D K E C L M G F B A
In-order: I H J D C K E A F L G M B

Steps to Build the Binary Tree:

1. Post-order tells us the root node. The last element is always the root.
Root: A
2. In the in-order sequence, locate the position of A . Elements to the left of A in the in-order
sequence are in the left subtree, and elements to the right are in the right subtree.
In-order (Left Subtree): I H J D C K E
In-order (Right Subtree): F L G M B
3. Continue recursively using the post-order sequence for the left and right subtrees.

Constructing the Tree:

From the post-order sequence, the element before A is B , which becomes the root of the right
subtree.
Continue the process to construct the entire tree.

Binary Tree for (ii):

A
/ \
C B
/ \
D F
/ \ / \
H E L G
/ \ / \
I J M B
\
K

Q6. Write a program in ‘C’ to implement a binary search tree (BST).

Traverse and display the binary search tree in the Inorder, Preorder
and Post order form.

Here’s a C program that implements a Binary Search Tree (BST) and provides functions to traverse and
display it in Inorder, Preorder, and Postorder:

C Program: Binary Search Tree with Traversals

#include <stdio.h> language-c

#include <stdlib.h>
// Definition of Node for BST
struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Function to create a new node

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

// Function to insert data in BST

struct Node* insert(struct Node* node, int data) {
// If the tree is empty, return a new node
if (node == NULL) return createNode(data);

// Otherwise, recur down the tree

if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);

// Return the unchanged node pointer

return node;
}

// Function to perform Inorder traversal (Left, Root, Right)

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

// Function to perform Preorder traversal (Root, Left, Right)

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

// Function to perform Postorder traversal (Left, Right, 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;
int n, data;

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

scanf("%d", &n);

printf("Enter the values to be inserted into BST:\n");

for (int i = 0; i < n; i++) {
scanf("%d", &data);
root = insert(root, data);
}

printf("\nInorder Traversal: ");

inorder(root);

printf("\nPreorder Traversal: ");

preorder(root);

printf("\nPostorder Traversal: ");

postorder(root);

return 0;
}

Explanation:
1. Node Structure: A Node structure contains an integer data and pointers to the left and right
child.
2. Insert Function: Inserts nodes in the correct position following the binary search tree property
(left child is smaller, right child is larger).
3. Inorder Traversal: Recursively visits the left subtree, the root, and then the right subtree.
4. Preorder Traversal: Visits the root, then recursively the left and right subtrees.
5. Postorder Traversal: Recursively visits the left and right subtrees, then the root.

Example Output:
Enter the number of nodes: 5
Enter the values to be inserted into BST:
50 30 20 40 70

Inorder Traversal: 20 30 40 50 70
Preorder Traversal: 50 30 20 40 70
Postorder Traversal: 20 40 30 70 50

This program inserts the given nodes into the BST and prints the traversals as per the requirements.
Q7. Define AVL tree. Create an AVL tree for the following list of data if
the data are inserted in the order in an empty AVL tree.
12, 5, 15, 20, 35, 8, 2, 40, 14, 24, 27, 45, 50, 3, 4

Further delete 2, 4, 5 and 12 from the above AVL tree.

AVL Tree Definition:

An AVL Tree is a type of self-balancing Binary Search Tree (BST) where the difference between the heights
of the left and right subtrees (called the balance factor) of any node is never more than one. If at any time, the
balance factor becomes more than 1 or less than -1, rotations (single or double) are performed to restore
balance.

AVL Tree Characteristics:

Balance Factor: For each node, it is defined as the difference between the heights of its left and right
subtrees. It should always be -1, 0, or 1.
Rotations: If a node becomes unbalanced, the tree performs one of the following rotations to restore
balance:
Right Rotation (Single Rotation)
Left Rotation (Single Rotation)
Left-Right Rotation (Double Rotation)
Right-Left Rotation (Double Rotation)

Steps for AVL Tree Insertion:

We will create the AVL tree by inserting the given data in the order and maintaining the tree balance through
rotations.

Given list of data (in the order to be inserted):

12, 5, 15, 20, 35, 8, 2, 40, 14, 24, 27, 45, 50, 3, 4

Code to Create an AVL Tree in C

#include <stdio.h> language-c

#include <stdlib.h>

// Definition of Node for AVL Tree

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

// Function to get height of a node

int height(struct Node* N) {
 if (N == NULL)
return 0;
return N->height;
}

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1; // New node is initially added at leaf
return newNode;
}

// Function to get the maximum of two integers

int max(int a, int b) {
return (a > b) ? a : b;
}

// Right Rotate
struct Node* rightRotate(struct Node* y) {
struct Node* x = y->left;
struct Node* T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;

// Return new root

return x;
}

// Left Rotate
struct Node* leftRotate(struct Node* x) {
struct Node* y = x->right;
struct Node* T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;

// Return new root

return y;
}

// Get Balance factor of node N

int getBalance(struct Node* N) {
 if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}

// Recursive function to insert a node in the subtree rooted with node and returns the new
root of the subtree
struct Node* insert(struct Node* node, int data) {
// 1. Perform the normal BST insertion
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 // Equal data is not allowed in BST
return node;

// 2. Update height of this ancestor node

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

// 3. Get the balance factor of this ancestor node to check whether this node became
unbalanced
int balance = getBalance(node);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case

if (balance > 1 && data < node->left->data)
return rightRotate(node);

// Right Right Case

if (balance < -1 && data > node->right->data)
return leftRotate(node);

// Left Right Case

if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right Left Case

if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}

// Return the (unchanged) node pointer

return node;
}

// Function to find the node with minimum value (used during deletion)
struct Node* minValueNode(struct Node* node) {
struct Node* current = node;
 // Loop down to find the leftmost leaf
while (current->left != NULL)
current = current->left;

return current;
}

// Recursive function to delete a node with given key from subtree with given root and
returns new root of subtree
struct Node* deleteNode(struct Node* root, int data) {
// STEP 1: PERFORM STANDARD BST DELETE
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 {
// Node with only one child or no child
if ((root->left == NULL) || (root->right == NULL)) {
struct Node* temp = root->left ? root->left : root->right;

// No child case
if (temp == NULL) {
temp = root;
root = NULL;
} else // One child case
*root = *temp; // Copy the contents of the non-empty child
free(temp);
} else {
// Node with two children: Get the inorder successor (smallest in the right
subtree)
struct Node* temp = minValueNode(root->right);

// Copy the inorder successor's data to this node

root->data = temp->data;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->data);
}
}

// If the tree had only one node, then return

if (root == NULL)
return root;

// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE

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

// STEP 3: GET THE BALANCE FACTOR OF THIS NODE TO CHECK WHETHER THIS NODE BECAME
UNBALANCED
int balance = getBalance(root);
 // If this node becomes unbalanced, then there are 4 cases

// Left Left Case

if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);

// Left Right Case

if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}

// Right Right Case

if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);

// Right Left Case

if (balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}

// Function to print the inorder traversal of the AVL tree

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;

// Inserting the given data

int data[] = {12, 5, 15, 20, 35, 8, 2, 40, 14, 24, 27, 45, 50, 3, 4};
int n = sizeof(data) / sizeof(data[0]);

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

root = insert(root, data[i]);

printf("Inorder traversal of the AVL tree: ");

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

// Deleting 2, 4, 5, and 12
root = deleteNode(root, 2);
root = deleteNode(root, 4);
root = deleteNode(root, 5);
root = deleteNode(root, 12);

printf("Inorder traversal after deletions: ");

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

return 0;
}

Explanation:
1. Node Structure: Each node contains the data, left and right pointers, and height.
2. Insert: Inserts data into the AVL tree, balancing the tree if necessary using rotations (left, right, left-
right, or right-left).
3. Delete:

Deletes a node while maintaining AVL properties.

4. Inorder Traversal: Used to print the tree contents in ascending order.

Output:
Inorder traversal of the AVL tree: 2 3 4 5 8 12 14 15 20 24 27 35 40 45 50
Inorder traversal after deletions: 3 8 14 15 20 24 27 35 40 45 50

In this program, after inserting the nodes and performing the deletions, the AVL tree remains balanced, as
demonstrated by the inorder traversal output.

B-tree Definition:
A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion,
deletion, and search operations. It is commonly used in databases and file systems. Unlike binary search
trees, B-trees can have multiple keys in each node and multiple children. B-trees help reduce the number of
disk accesses required during search operations.

Properties of B-trees:
1. Order: The order m of a B-tree defines the maximum number of children each node can have. In a
B-tree of order m :
Each internal node can have at most m children.
Each internal node (except the root) must have at least ⌈m/2⌉ children.
The root must have at least 2 children if it is not a leaf.
A node can contain at most m-1 keys.
All leaves appear on the same level.
2. Keys:
Each internal node contains n keys, where ⌈m/2⌉ - 1 ≤ n ≤ m - 1 .
Keys within a node are arranged in ascending order.
 3. Search: Searching in a B-tree starts from the root and follows a path that resembles binary search
but works across multiple keys and children.
4. Insertion:
When a node is full (i.e., it has m-1 keys), it is split into two nodes. The middle key is moved up
to the parent node.
This process may propagate upwards, potentially causing the root to split and increase the
height of the tree.
5. Deletion:
Deleting a key may require merging nodes or borrowing keys from siblings to maintain the
properties of the B-tree.

Creating a B-tree of Order 5:

Order 5 means each node can have a maximum of 4 keys and 5 children.

Sequence to insert:

12, 5, 15, 20, 60, 45, 35, 40, 25, 8, 7, 55, 50, 66, 65, 80

Step-by-step Insertion Process:

1. Insert 12: Root node is created with 12.
2. Insert 5: Add 5 to the root node. Now the root has keys [5, 12].
3. Insert 15: Add 15 to the root. Now the root has keys [5, 12, 15].
4. Insert 20: Add 20 to the root. Now the root has keys [5, 12, 15, 20].
5. Insert 60: Add 60 to the root. Now the root has [5, 12, 15, 20, 60], which is full (4 keys).
6. Node Split: The middle key 15 moves up, splitting the root into two nodes:
Root: [15]
Left Child: [5, 12]
Right Child: [20, 60]
7. Insert 45: Insert 45 into the right child, now it becomes [20, 45, 60].
8. Insert 35: Insert 35 into the right child, now it becomes [20, 35, 45, 60].
9. Insert 40: Insert 40 into the right child, now it becomes [20, 35, 40, 45, 60] (full).
10. Node Split: The middle key 40 moves up to the root. The tree now looks like:
Root: [15, 40]
Left Child: [5, 12]
Middle Child: [20, 35]
Right Child: [45, 60]
11. Insert 25: Insert 25 into the middle child, now it becomes [20, 25, 35].
12. Insert 8: Insert 8 into the left child, now it becomes [5, 8, 12].
13. Insert 7: Insert 7 into the left child, now it becomes [5, 7, 8, 12].
14. Insert 55: Insert 55 into the right child, now it becomes [45, 55, 60].
15. Insert 50: Insert 50 into the right child, now it becomes [45, 50, 55, 60].
16. Insert 66: Insert 66 into the right child, now it becomes [45, 50, 55, 60, 66] (full).
17. Node Split: The middle key 55 moves up to the root. The tree now looks like:
Root: [15, 40, 55]
Left Child: [5, 7, 8, 12]
 Middle Left Child: [20, 25, 35]
Middle Right Child: [45, 50]
Right Child: [60, 66]
18. Insert 65: Insert 65 into the right child, now it becomes [60, 65, 66].
19. Insert 80: Insert 80 into the right child, now it becomes [60, 65, 66, 80].

Deletions:
1. Delete 5: Remove 5 from the left child, now it becomes [7, 8, 12].
2. Delete 12: Remove 12 from the left child, now it becomes [7, 8].
3. Delete 8: Remove 8 from the left child. After deletion, we need to merge nodes since the node
becomes underfull (fewer than 2 keys). The result is:
Left Child: [7]
4. Delete 20: Remove 20 from the middle left child. After deletion, the middle left child becomes [25,
35].

Final B-tree Structure after Insertions and Deletions:

Root: [40, 55]
Left Child: [7, 25, 35]
Middle Child: [45, 50]
Right Child: [60, 65, 66, 80]

This is the final balanced B-tree after all the operations.

B-tree Visualization (Order-5) after Insertions:

[40, 55]
/ | \
[7, 25, 35] [45, 50] [60, 65, 66, 80]

B-tree Visualization after Deletions:

[40, 55]
/ | \
[7, 25, 35] [45, 50] [60, 65, 66, 80]

This final structure satisfies all the properties of a B-tree of order 5.

To apply Dijkstra's algorithm to the given graph and find the shortest path from the vertex 'S' to all other
vertices, we'll go step by step. Here's the approach:

Step-by-Step Process:
1. Initialize:

Set the initial distances from 'S' to all other vertices as infinite ( ∞ ), except for the starting
vertex 'S' itself, which has a distance of 0.

Initial distances:
S = 0, A = ∞, B = ∞, C = ∞, D = ∞

2. Process the Starting Node (S):

The current node is 'S'. Explore all edges from 'S' and update the distances to its neighbors.
From 'S' to 'A': 10 units (S → A = 10)
From 'S' to 'C': 5 units (S → C = 5)
From 'S' to 'D': 7 units (S → D = 7)

Updated distances:
S = 0, A = 10, B = ∞, C = 5, D = 7

3. Select the Next Node:

The next node is the one with the smallest distance that hasn't been processed yet. This is 'C'
(distance 5).
Explore all edges from 'C'.
From 'C' to 'A': C → A = 5 + 3 = 8 (updated because 8 < 10)
From 'C' to 'D': C → D = 5 + 2 = 7 (already the same as current distance to D)

Updated distances:
S = 0, A = 8, B = ∞, C = 5, D = 7

4. Select the Next Node:

The next node is 'D' (distance 7).

Explore all edges from 'D'.
From 'D' to 'B': D → B = 7 + 6 = 13 (updated distance to B)

Updated distances:
 S = 0, A = 8, B = 13, C = 5, D = 7

5. Select the Next Node:

The next node is 'A' (distance 8).

Explore all edges from 'A'.
From 'A' to 'B': A → B = 8 + 1 = 9 (updated because 9 < 13)

Updated distances:
S = 0, A = 8, B = 9, C = 5, D = 7

6. Select the Next Node:

The last node to process is 'B' (distance 9). There are no updates to be made from 'B', as all its
neighbors already have shorter paths.

Final Shortest Path Distances:

S → A = 8
S → B = 9
S → C = 5
S → D = 7

Shortest Paths:
S → A: S → C → A (total distance = 8)
S → B: S → C → A → B (total distance = 9)
S → C: S → C (total distance = 5)
S → D: S → D (total distance = 7)

To apply Prim's Algorithm to the given graph and find the Minimum Spanning Tree (MST), we will
proceed step by step.

Prim's Algorithm Explanation:

Prim's Algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST) of a graph by selecting
the smallest weight edges that connect a set of visited vertices to unvisited vertices, ensuring no cycles are
formed.
Steps for Prim's Algorithm:
1. Initialization: Start with any vertex as part of the MST. In this example, let's begin with vertex 0.
Initially, the MST set contains only vertex 0, and the remaining vertices are unvisited.
2. Edge Selection: From the current MST set, pick the smallest edge that connects a visited vertex to
an unvisited vertex. Add that edge and the unvisited vertex to the MST.
3. Repeat: Repeat the process of selecting the smallest edge until all vertices are included in the MST.

Step-by-Step Process on the Given Graph:

Graph Data:
Vertices: 0, 1, 2, 3, 4, 5, 6, 7, 8
Edges with weights (u - v: weight):
0 - 1: 4, 0 - 7: 8
1 - 7: 11, 1 - 2: 8
7 - 8: 7, 7 - 6: 1, 7 - 0: 8
2 - 8: 2, 2 - 3: 7, 2 - 5: 4
8 - 6: 6, 8 - 2: 2, 8 - 7: 7
6 - 5: 2, 6 - 7: 1, 6 - 8: 6
3 - 4: 9, 3 - 5: 14
5 - 4: 10, 5 - 6: 2

Execution:

Step 1: Start with vertex 0

The edges from vertex 0 are:
(0, 1) with weight 4
(0, 7) with weight 8
Choose the minimum weight edge (0, 1), so add vertex 1 and the edge (0, 1) to the MST.

MST edges so far:

0 - 1: 4

Step 2: Explore from vertex 1

The edges from the MST set (vertices 0 and 1) are:
(1, 7) with weight 11
(1, 2) with weight 8
(0, 7) with weight 8
Choose the minimum weight edge (0, 7), so add vertex 7 and the edge (0, 7) to the MST.

MST edges so far:

0 - 1: 4
0 - 7: 8

Step 3: Explore from vertex 7

 The edges from the MST set (vertices 0, 1, and 7) are:
(1, 2) with weight 8
(7, 8) with weight 7
(7, 6) with weight 1
Choose the minimum weight edge (7, 6), so add vertex 6 and the edge (7, 6) to the MST.

MST edges so far:

0 - 1: 4
0 - 7: 8
7 - 6: 1

Step 4: Explore from vertex 6

The edges from the MST set (vertices 0, 1, 6, and 7) are:
(6, 5) with weight 2
(7, 8) with weight 7
(1, 2) with weight 8
(6, 8) with weight 6
Choose the minimum weight edge (6, 5), so add vertex 5 and the edge (6, 5) to the MST.

MST edges so far:

0 - 1: 4
0 - 7: 8
7 - 6: 1
6 - 5: 2

Step 5: Explore from vertex 5

The edges from the MST set (vertices 0, 1, 5, 6, and 7) are:
(5, 4) with weight 10
(2, 3) with weight 7
(7, 8) with weight 7
(6, 8) with weight 6
(1, 2) with weight 8
Choose the minimum weight edge (6, 8), so add vertex 8 and the edge (6, 8) to the MST.

MST edges so far:

0 - 1: 4
0 - 7: 8
7 - 6: 1
6 - 5: 2
6 - 8: 6

Step 6: Explore from vertex 8

The edges from the MST set (vertices 0, 1, 5, 6, 7, and 8) are:
(2, 8) with weight 2
(1, 2) with weight 8
 (2, 3) with weight 7
Choose the minimum weight edge (2, 8), so add vertex 2 and the edge (2, 8) to the MST.

MST edges so far:

0 - 1: 4
0 - 7: 8
7 - 6: 1
6 - 5: 2
6 - 8: 6
2 - 8: 2

Step 7: Explore from vertex 2

The only edge left is (2, 3) with weight 7, so add vertex 3 and the edge (2, 3) to the MST.

MST edges so far:

0 - 1: 4
0 - 7: 8
7 - 6: 1
6 - 5: 2
6 - 8: 6
2 - 8: 2
2 - 3: 7

Step 8: Explore from vertex 3

The only edge left is (3, 4) with weight 9, so add vertex 4 and the edge (3, 4) to the MST.

Final MST edges:

0 - 1: 4
0 - 7: 8
7 - 6: 1
6 - 5: 2
6 - 8: 6
2 - 8: 2
2 - 3: 7
3 - 4: 9

Minimum Spanning Tree:

The MST includes the following edges:

(0, 1) with weight 4

(0, 7) with weight 8
(7, 6) with weight 1
(6, 5) with weight 2
(6, 8) with weight 6
(2, 8) with weight 2
(2, 3) with weight 7
 (3, 4) with weight 9

Total Weight of MST:

4 + 8 + 1 + 2 + 6 + 2 + 7 + 9 = 39

Thus, the total weight of the Minimum Spanning Tree is 39.

Q11: Apply Insertion and Selection Sorting Algorithms

We are given a list of items to sort using Insertion Sort and Selection Sort:

12, 5, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7

Let’s go through the intermediate steps of both algorithms and analyze their time complexity.

Insertion Sort
Insertion Sort works by building a sorted section of the list one element at a time by repeatedly inserting
the next unsorted element into its correct position in the sorted section.

Initial List:
12, 5, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7

Step-by-step Process:
Start with the second element (5). Compare with 12, and since 5 < 12, move 12 to the right and insert 5
at the start.
5, 12, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7

Next, take 2. Compare with 12 and 5, shift them to the right and insert 2 at the start.
2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7

Now take 15. It's greater than 12, so no movement is needed.

2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7

Take 25. It's greater than 15, so no movement is needed.

2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7

Take 30. No movement is needed.

2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7

Take 45. No movement is needed.

 2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7

Take 8. Compare it with 45, 30, 25, 15, and so on. Shift all these elements to the right and insert 8
between 5 and 12.
2, 5, 8, 12, 15, 25, 30, 45, 17, 50, 3, 7

Take 17. Shift 45 and 30 to the right, then insert 17 between 15 and 25.
2, 5, 8, 12, 15, 17, 25, 30, 45, 50, 3, 7

Take 50. No movement is needed.

2, 5, 8, 12, 15, 17, 25, 30, 45, 50, 3, 7

Take 3. Shift all the elements larger than 3 to the right and insert 3 at the second position.
2, 3, 5, 8, 12, 15, 17, 25, 30, 45, 50, 7

Finally, take 7. Shift 50, 45, 30, 25, 17, 15, 12, and 8 to the right, then insert 7 between 5 and 8.
2, 3, 5, 7, 8, 12, 15, 17, 25, 30, 45, 50

Final Sorted List:

2, 3, 5, 7, 8, 12, 15, 17, 25, 30, 45, 50

Selection Sort
Selection Sort works by selecting the smallest element from the unsorted portion of the list and swapping it
with the first element of the unsorted portion. Then repeat the process for the next unsorted part of the list.

Initial List:
12, 5, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7

Step-by-step Process:
In the first pass, find the smallest element (2) and swap it with the first element (12).
2, 5, 12, 15, 25, 30, 45, 8, 17, 50, 3, 7

In the second pass, the next smallest element is 3. Swap 3 with 5.

2, 3, 12, 15, 25, 30, 45, 8, 17, 50, 5, 7

In the third pass, the next smallest element is 5. No swap is needed.

2, 3, 5, 15, 25, 30, 45, 8, 17, 50, 12, 7

In the fourth pass, the next smallest element is 7. Swap 7 with 15.
2, 3, 5, 7, 25, 30, 45, 8, 17, 50, 12, 15

In the fifth pass, the next smallest element is 8. Swap 8 with 25.
 2, 3, 5, 7, 8, 30, 45, 25, 17, 50, 12, 15

In the sixth pass, the next smallest element is 12. Swap 12 with 30.
2, 3, 5, 7, 8, 12, 45, 25, 17, 50, 30, 15

In the seventh pass, the next smallest element is 15. Swap 15 with 45.
2, 3, 5, 7, 8, 12, 15, 25, 17, 50, 30, 45

In the eighth pass, the next smallest element is 17. Swap 17 with 25.
2, 3, 5, 7, 8, 12, 15, 17, 25, 50, 30, 45

In the ninth pass, the next smallest element is 25. No swap is needed.
2, 3, 5, 7, 8, 12, 15, 17, 25, 50, 30, 45

In the tenth pass, the next smallest element is 30. Swap 30 with 50.
2, 3, 5, 7, 8, 12, 15, 17, 25, 30, 50, 45

In the eleventh pass, the next smallest element is 45. Swap 45 with 50.
2, 3, 5, 7, 8, 12, 15, 17, 25, 30, 45, 50

Final Sorted List:

2, 3, 5, 7, 8, 12, 15, 17, 25, 30, 45, 50

Time Complexity Analysis:

Insertion Sort:
Best case: O(n) - When the array is already sorted.
Worst case: O(n²) - When the array is sorted in reverse order.
Average case: O(n²) - When the array is randomly ordered.

Selection Sort:
Best case: O(n²) - Selection sort always takes O(n²) because it scans the entire list to find the
minimum.
Worst case: O(n²) - Selection sort always takes O(n²), regardless of input.
Average case: O(n²) - The algorithm is insensitive to the initial ordering of the list.

Both algorithms sort the list in ascending order, but Insertion Sort tends to perform better on nearly
sorted data, whereas Selection Sort performs the same regardless of the initial order of the data.
Q12: Heap Tree and Heap Sort

What is a Heap Tree?

A Heap Tree is a complete binary tree that satisfies the heap property:

In a Max Heap, the value of each node is greater than or equal to the values of its children, making the
largest element the root.
In a Min Heap, the value of each node is smaller than or equal to its children, making the smallest
element the root.

Steps to Create a Max Heap

Given the list of elements:
10, 20, 5, 25, 30, 18, 3, 70, 55, 45, 12, 24

We will build the Max Heap by inserting elements one by one and ensuring the heap property is maintained
by heapifying the tree.

Step-by-Step Construction of the Max Heap

1. Insert 10:
Heap:

10

2. Insert 20:
Compare 20 with 10. Since 20 > 10, swap them.
Heap:

20
/
10

3. Insert 5:
Heap:

20
/ \
10 5

4. Insert 25:
Compare 25 with 10. Swap 25 and 10. Then compare 25 with 20. Swap 25 and 20.
Heap:

25
/ \
20 5
/
10

5. Insert 30:
Compare 30 with 20. Swap 30 and 20. Then compare 30 with 25. Swap 30 and 25.
Heap:

30
/ \
25 5
/
10 20

6. Insert 18:
Heap:

30
/ \
25 18
/ \
10 20 5

7. Insert 3:
Heap:

30
/ \
25 18
/ \ \
10 20 5
/
3

8. Insert 70:
Compare 70 with 10. Swap them. Then compare 70 with 25. Swap them. Then compare 70 with 30. Swap 70
and 30.
Heap:

70
/ \
30 18
/ \ \
25 20 5
/ \
3 10

9. Insert 55:
Compare 55 with 25. Swap them. Then compare 55 with 30. Swap them.
Heap:

70
/ \
55 18
/ \ \
30 20 5
/ \
3 10 25

10. Insert 45:

Compare 45 with 30. Swap them.
Heap:

70
/ \
55 18
/ \ \
45 20 5
/ \
3 10 25

11. Insert 12:

Heap:

70
/ \
55 18
/ \ \
45 20 5
/ \ \
3 10 25 12

12. Insert 24:

Compare 24 with 20. Swap them.
Heap:

70
/ \
55 18
/ \ \
45 24 5
/ \ \
3 10 25 12

Heap Sort Explanation

After building the Max Heap, we can use Heap Sort to sort the array.

Steps for Heap Sort:

1. Swap the root (largest element) with the last element of the heap.
2. Reduce the size of the heap by 1.
3. Restore the heap property by heapifying the root.
4. Repeat this process until the entire array is sorted.
Heap Sort Process Example:
1. Initial Max Heap:
70, 55, 18, 45, 24, 5, 3, 10, 25, 12

2. Swap 70 and 12, then heapify:

55, 45, 18, 12, 24, 5, 3, 10, 25

3. Swap 55 and 25, then heapify:

45, 25, 18, 12, 24, 5, 3, 10

4. Swap 45 and 10, then heapify:

25, 10, 18, 12, 24, 5, 3

Continue swapping and heapifying until the entire array is sorted.

Time Complexity of Heap Sort:

Best Case: O(n log n)
Worst Case: O(n log n)
Average Case: O(n log n)

Heap Sort has a consistent time complexity of O(n log n) in all cases since the heap operations are always
logarithmic and occur for every element.

Q13. Write a program in ‘C’ language for 2-way merge sort.

Q13: 2-Way Merge Sort in C

Merge Sort is a divide-and-conquer sorting algorithm. It divides the array into two halves, recursively sorts
them, and then merges the two sorted halves into a single sorted array.

The 2-way merge sort splits the array into two parts, sorts each part, and then merges the two sorted
arrays.

Steps in Merge Sort:

1. Divide the array into two halves.
2. Recursively sort the two halves.
3. Merge the two sorted halves.

C Program for 2-Way Merge Sort

#include <stdio.h> language-c

// Function to merge two halves into a sorted array

void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // Size of the left subarray
int n2 = right - mid; // Size of the right subarray

// Create temporary arrays

int L[n1], R[n2];

// Copy data to temporary arrays L[] and R[]

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];

// Initial indexes of the subarrays

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

// Merge the temp arrays back into arr[]

while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy the remaining elements of L[], if any

while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// Copy the remaining elements of R[], if any

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// Function to implement merge sort

void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the middle point
int mid = left + (right - left) / 2;

// Recursively sort first and second halves

mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);

// Merge the sorted halves

merge(arr, left, mid, right);
}
}

// Function to print the array

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

// Main function to run the merge sort

int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array: \n");

printArray(arr, arr_size);

// Apply merge sort

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array: \n");

printArray(arr, arr_size);

return 0;
}

Explanation:
1. merge() function:
This function merges two subarrays: L[] (left) and R[] (right).
It compares elements from both arrays and stores the smaller one into the original array
arr[] .
2. mergeSort() function:
This is a recursive function that splits the array in two halves, sorts them, and then merges
them back.
3. printArray() function:
This function is used to display the array before and after sorting.

Sample Output:
Given array:
12 11 13 5 6 7

Sorted array:
5 6 7 11 12 13

Time Complexity:
Best Case: O(n log n)
Worst Case: O(n log n)
 Average Case: O(n log n)

Merge sort has a consistent time complexity of O(n log n) for all cases since it always divides the array into
two and merges them, which is logarithmic in nature.

Q14. What is Splay tree? Explain the Zig zag and Zag zig rotations in
Splay tree with the help of a suitable example.
Splay Tree:

A splay tree is a self-adjusting binary search tree where recently accessed elements are moved closer to the
root through a series of rotations. This helps in optimizing access time for frequently accessed elements,
making the tree adaptively efficient. The key operation of a splay tree is splaying, which involves performing
rotations to move a particular node to the root.

Types of Rotations:
There are three types of rotations performed during splaying:

1. Zig rotation (single rotation)

2. Zig-Zig rotation (double rotation in the same direction)
3. Zig-Zag rotation (double rotation in opposite directions)

Let's focus on Zig-Zag and Zag-Zig rotations.

Zig-Zag Rotation (Left-Right Rotation):

A Zig-Zag rotation occurs when the node we are accessing is a right child of a left child of its grandparent.
In this case, two rotations are performed:

1. First, a left rotation is performed on the node's parent.

2. Then, a right rotation is performed on the grandparent.

Example:

Let's assume the following tree structure:

10
/
5
\
8

If we want to access node 8, the structure would look like this:

Node 8 is the right child of 5 (left child of 10), so we need to perform a Zig-Zag rotation.

Steps:

1. First, perform a left rotation on node 5:

10
/
8
 /
5
2. Now, perform a right rotation on node 10:
8
/ \
5 10

After the Zig-Zag rotation, node 8 is moved to the root.

Zag-Zig Rotation (Right-Left Rotation):

A Zag-Zig rotation occurs when the node we are accessing is a left child of a right child of its grandparent.
Similar to Zig-Zag, two rotations are performed:

1. First, a right rotation is performed on the node's parent.

2. Then, a left rotation is performed on the grandparent.

Example:

Let's assume the following tree structure:

10
\
15
/
12

If we want to access node 12, we perform a Zag-Zig rotation.

Steps:

1. First, perform a right rotation on node 15:

10
\
12
\
15

2. Now, perform a left rotation on node 10:

12
/ \
10 15

After the Zag-Zig rotation, node 12 is moved to the root.

Q15. What is Red-Black tree? Explain insertion and deletion operations

in a Red-Black tree with the help of a suitable example.
A Red-Black Tree is a type of self-balancing binary search tree where each node has an extra bit for
denoting the color of the node, either red or black. The balancing of the tree ensures that the path from the
root to the farthest leaf is not more than twice as long as the path from the root to the nearest leaf,
maintaining the time complexity for search operations at O(log n).

Properties of a Red-Black Tree:

1. Every node is either red or black.
2. The root is always black.
3. All leaves (NIL or NULL nodes) are considered black.
4. If a node is red, both its children must be black. (No two red nodes can be adjacent.)
5. Every path from a node to its descendant NULL nodes must have the same number of
black nodes.

These properties ensure that the tree remains approximately balanced.

Insertion in Red-Black Tree:

Insertion in a Red-Black Tree is similar to that in a Binary Search Tree, but with some additional steps to
ensure the tree remains balanced and follows Red-Black properties.

Steps for Insertion:

1. Standard BST Insertion: Insert the node at the correct position as in a regular Binary Search
Tree.
2. Color the new node red: Initially, we color the new node as red.
3. Fix violations: If the insertion violates the Red-Black Tree properties (like two consecutive red
nodes), we fix the tree by recoloring and rotations.

Example:
Suppose we insert a new node into the following Red-Black Tree:

Before Insertion:

10 (Black)
/ \
5 (Red) 20 (Black)

Let’s insert 15 :

1. We first insert it as we would in a BST:

10 (Black)
/ \
5 (Red) 20 (Black)
/
15 (Red)

2. Since 15 is red and its parent 20 is black, no property is violated. Thus, no further changes are
required.

Now, let's take a case where violation occurs.

If we insert 25 :

10 (Black)
/ \
5 (Red) 20 (Black)
/
15 (Red)
\
25 (Red)

Here, the new node 25 is red and its parent 15 is also red, violating the Red-Black Tree property that no two
consecutive nodes can be red. To fix this:

We recolor: Make 20 red and 15 and 25 black, or

Rotate: Apply a left rotation on node 20 to balance the tree.

Deletion in Red-Black Tree:

Deletion is a bit more complex because after removing a node, we need to ensure that the Red-Black Tree
properties are maintained.

Steps for Deletion:

1. Standard BST Deletion: Remove the node as in a Binary Search Tree.
2. Fix Double Black: After deletion, a double-black situation might arise (when a black node is
removed or a red node is replaced by a black node). To fix this, we use recoloring or rotations.

Example:
Consider the tree:

10 (Black)
/ \
5 (Black) 20 (Black)
/
15 (Red)

If we delete node 15 :

10 (Black)
/ \
5 (Black) 20 (Black)

Since 15 was red, its deletion doesn’t violate any Red-Black Tree properties.

However, if we delete a black node like 5 :

10 (Black)
\
 20 (Black)

Now, node 10 has one black child and one NIL (black) child, maintaining the black height. No further
adjustments are needed.

In more complex scenarios, a series of rotations and recoloring operations may be required to fix the tree
after deletions.

Rotations:
Left Rotation: Used when the right subtree is "heavier" or needs to be balanced with the left subtree.
Right Rotation: Used when the left subtree is "heavier" or needs balancing.

Time Complexity:
Insertion/Deletion: O(log n)
Search: O(log n)

The balancing properties of the Red-Black Tree ensure that these operations remain efficient even in the
worst case.

Q16. Explain Direct File and Indexed Sequential File Organization.

Direct File Organization:

Direct file organization (also called hash file organization) is a file system structure where records are
stored at a specific location determined by applying a hash function to the key field of the record. This allows
for quick access to data, as the exact location of the record can be determined without sequentially searching
through the file.

Characteristics:
Records are accessed directly through a hash function applied to the record's key.
No sequential search is required; data can be accessed in constant time ( O(1) ), making this method
efficient for large databases.
Collisions may occur when two different keys map to the same location, which is handled by
techniques like open addressing or chaining.

Advantages:
Fast access to records.
Efficient when the key is known and direct access is required.

Disadvantages:
Handling collisions can be complex.
Wasted space may occur if many hash locations are unused (sparse distribution).
Inefficient for range queries (when you need to access records sequentially).
Indexed Sequential File Organization:
Indexed sequential file organization combines the features of both sequential and direct access file
organizations. It maintains records in a sequential order but adds an index to speed up access to records.

Structure:
1. Data File: Contains records in sequential order based on a key field (like a sorted list).
2. Index File: Contains key fields and pointers to records in the data file. This acts like a lookup table
that speeds up searching for specific records.

Characteristics:
Data is stored sequentially (sorted by key).
An index is maintained, which provides direct access to a subset of records, reducing the time to
search.
If a key is not found directly in the index, a sequential search is performed within a block of records.

Advantages:
Faster access to records due to the use of an index.
Supports both sequential and direct access, making it versatile for various use cases.
Efficient for range queries, as records are sorted.

Disadvantages:
More storage is required to maintain the index.
Overhead for maintaining the index during insertions and deletions.
Slower access compared to purely direct file organization, especially if the index becomes large.

Comparison:
Feature Direct File Organization Indexed Sequential File
Organization
Access Method Direct (through hashing) Sequential + Indexed
Search Time ( O(1) ) (constant time) Fast via index, sequential search for non-
indexed records
Efficient for Exact record access Range queries and partial key searches
Index Maintenance Not required Required
Storage Efficiency May waste space due to collisions or Uses extra storage for the index
unused hash locations
Insertion/Deletion Hash collisions must be handled Index needs updating
Complexity
Use Cases Fast lookups when key is known Mixed queries (exact + range queries)