SWE-509: Advanced Data Structure and

Algorithms Lab Practical File

Submitted towards the partial fulfillment of the requirements

of the award of the degree of

Master of Technology
In Software
Engineering

Submitted by
ADITYA PANDEY
24/SWE/10
I SEM, I YEAR

Submitted to
Ms. Shweta Meena
Assistant Professor
Department of Software Engineering

Delhi Technological University

(Formerly Delhi College of Engineering)
Bawana Road, New Delhi - 110042
 INDEX

S.No Experiment Name Date Page No. Signature

1. Write a program that use both recursive and non-recursive 1
functions for implementing the following searching methods:
a) Linear search b) Binary search
2. Write a program to implement the following using an array. 4
a) Stack ADT b) Queue ADT
3. Write a program that reads an infix expression and 7
converts the expression to postfix form. (Use stack ADT).
4. Write a program to implement the following using a singly 10
linked list. a) Stack ADT b) Queue ADT
5. Write a program to perform the following 14
operations: a)Construct a binary search tree of
elements.
b) Search for a key element in the above binary search tree.
c) Delete an element from the above binary search tree.
6. Write a program to implement all the functions of a 18
dictionary (ADT) using Hashing

7. Write a program that use recursive and non-non-recursive 22

functions to traverse the given binary tree in a) Preorder b)
Inorder c) Postorder
8. Write a program for the implementation of BFS BFS and 27
DFS for a graph.
9. Write a program for the implementation of the following 30
sorting methods: a) Bubble sort b) Insertion sort c) Quick
sort d) Merge sort e) Heap sort f) Radix sort g) Binary tree
sort
10. Write a program to perform the following operations: 37
(a) Insertion into a B-tree (b) Searching in a B-tree (c)
Delete an element from a B-tree.
11. Write a program to perform the following operations: 45
a) Insert an element into a Min-Max heap.
b) Delete an element from a Min-Max heap.
c) Search for a key element in a Min-Max heap
12. Write a program to perform the following operations: 49
a) Insert an element into a AVL tree.
b) Delete an element from a AVL search tree.
 EXPERIMENT - 1
AIM: Write a program that use both recursive and non-recursive functions for implementing the
following searching methods: a) Linear search b) Binary search

THEORY:

Linear Search:
In Linear Search, we iterate over all the elements of the array and check if the current element is equal
to the target element. If we find any element to be equal to the target element, then return the index of
the current element.

Binary Search:
A binary search is a search in which the middle element is calculated to check whether it is smaller or
larger than the element which is to be searched. The main advantage of using binary search is that it
does not scan each element in the list. Instead of scanning each element, it performs the searching to
the half of the list. So, the binary search takes less time to search an element as compared to a linear
search. The one pre-requisite of binary search is that an array should be in sorted order.

SOURCE CODE:
#include <bits/stdc++.h>
using namespace std;

void printarr(vector<int>& arr) {

for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << endl;
}

void linearSearchIterative(vector<int>& arr, int key) {

for (int i = 0; i < arr.size(); i++) {
if (arr[i] == key) {
cout << "Key found at index: " << i << endl;
return;
}
}
cout << "Key not found" << endl;
}

void linearSearchRecursive(vector<int>& arr, int key, int i) {

if (i >= arr.size()) {
cout << "Key not found" << endl;
return;
}
if (arr[i] == key) {
ADITYA PANDEY 24/SWE/
3 10
 cout << "Key found at index: " << i << endl;
return;
}
linearSearchRecursive(arr, key, i + 1);
}

void binarySearchIterative(vector<int>& arr, int key) {

int s = 0, e = arr.size() - 1;
while (s <= e) {
int mid = s + (e - s) / 2;
if (arr[mid] == key) {
cout << "Key found at index: " << mid << endl;
return;
}
else if (arr[mid] < key) {
s = mid + 1;
}
else {
e = mid - 1;
}
}
cout << "Key not found" << endl;
}

void binarySearchRecursive(vector<int>& arr, int s, int e, int key) {

if (s > e) {
cout << "Key not found" << endl;
return;
}
int mid = s + (e - s) / 2;
if (arr[mid] == key) {
cout << "Key found at index: " << mid << endl;
return;
}
else if (arr[mid] < key) {
binarySearchRecursive(arr, mid + 1, e, key);
}
else {
binarySearchRecursive(arr, s, mid - 1, key);
}
}

int main() {
cout << "Name: ADITYA PANDEY\nRoll NO.: 24/SWE/10\n" << endl;

int n;
cout << "Enter the number of elements in the array: ";
cin >> n;

vector<int> arr(n);
ADITYA PANDEY 24/SWE/
4 10
 cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}

int key;
cout << "Enter the key to search: ";
cin >> key;

cout << "\nArray: ";

printarr(arr);

cout << "\nLinear search Iteratively:" << endl;

linearSearchIterative(arr, key);

cout << "Linear search Recursively:" << endl;

linearSearchRecursive(arr, key, 0);

// Sorting the array for binary search as it requires sorted data

sort(arr.begin(), arr.end());
cout << "\nArray (sorted for binary search): ";
printarr(arr);

cout << "Binary search Iteratively:" << endl;

binarySearchIterative(arr, key);

cout << "Binary search Recursively:" << endl;

binarySearchRecursive(arr, 0, arr.size() - 1, key);

return 0;
}
OUTPUT:

ADITYA PANDEY 24/SWE/

5 10
LEARNINGS:

1. Linear Search is simple but less efficient for large datasets, as it checks each element sequentially.
2. Binary Search is more efficient with sorted arrays, dividing the search space with each comparison.
3. Recursive implementations use the call stack for iteration, which may lead to higher memory
usage but can be more concise.
4. Non-recursive methods avoid the overhead of recursion, which can be beneficial for larger data sets.

ADITYA PANDEY 24/SWE/

6 10
 EXPERIMENT - 2
AIM: Write a program to implement the following using an array. a) Stack ADT b) Queue ADT

THEORY:
STACK:
A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that
the last element added to the stack is the first one to be removed. Think of a stack of plates – you add
new plates on top, and you take plates from the top.

Operations on Stack
Push: Add an element to the top of the stack.
Pop: Remove the element from the top of the stack.
Peek (or Top): Retrieve the element at the top of the stack without removing it.
isEmpty: Check if the stack is empty.
isFull: Check if the stack is full (only relevant for a fixed-size stack implemented using an array).

QUEUE:
A Queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that
the first element added to the queue is the first one to be removed. A queue is similar to a line of
people; people join from the back and leave from the front.

Operations on Queue:
Enqueue: Add an element to the end (rear) of the queue.
Dequeue: Remove an element from the front of the queue.
Front: Retrieve the element at the front without removing
it. isEmpty: Check if the queue is empty.
isFull: Check if the queue is full (only relevant for a fixed-size queue implemented using an array).

SOURCE CODE:
#include <iostream>
using namespace std;

#define MAX 100

class Stack {
int top;
int arr[MAX];

public:
Stack() { top = -1; }

bool isFull() { return top == MAX - 1; }

bool isEmpty() { return top == -1; }

void push(int x) {
ADITYA PANDEY 24/SWE/
7 10
 if (isFull()) {
cout << "Stack Overflow\n";
return;
}
arr[++top] = x;
}

int pop() {
if (isEmpty()) {
cout << "Stack Underflow\n";
return -1;
}
return arr[top--];
}

int peek() {
if (isEmpty()) {
cout << "Stack is Empty\n";
return -1;
}
return arr[top];
}
};

class Queue {
int front, rear;
int arr[MAX];

public:
Queue() { front = rear = -1; }

bool isFull() { return rear == MAX - 1; }

bool isEmpty() { return front == -1 || front > rear; }

void enqueue(int x) {
if (isFull()) {
cout << "Queue Overflow\n";
return;
}
if (front == -1) front = 0;
arr[++rear] = x;
}

int dequeue() {
if (isEmpty()) {
cout << "Queue Underflow\n";
return -1;
}
return arr[front++];
}

ADITYA PANDEY 24/SWE/

8 10
 int peek() {
if (isEmpty()) {
cout << "Queue is Empty\n";
return -1;
}
return arr[front];
}
};

int main() {
Stack s;
Queue q;
int choice, value;

while (true) {
cout << "\nChoose an operation:\n";
cout << "1. Push to Stack\n";
cout << "2. Pop from Stack\n";
cout << "3. Peek Stack\n";
cout << "4. Enqueue to Queue\n";
cout << "5. Dequeue from Queue\n";
cout << "6. Peek Queue\n";
cout << "0. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to push onto the stack: ";
cin >> value;
s.push(value);
break;
case 2:
cout << "Popped from Stack: " << s.pop() << endl;
break;
case 3:
cout << "Top of Stack: " << s.peek() << endl;
break;
case 4:
cout << "Enter value to enqueue to the queue: ";
cin >> value;
q.enqueue(value);
break;
case 5:
cout << "Dequeued from Queue: " << q.dequeue() << endl;
break;
case 6:
cout << "Front of Queue: " << q.peek() << endl;
break;
case 0:
cout << "Exiting program.\n";
ADITYA PANDEY 24/SWE/
9 10
 return 0;
default:
cout << "Invalid choice. Try again.\n";
}
}

return 0;
}

OUTPUT:

LEARNINGS:
1. Stack ADT is useful in scenarios where LIFO access is required, such as function call
stacks or undo mechanisms in software.
2. Queue ADT is effective for FIFO access, suitable for task scheduling, buffering, and realtime
processing applications.
3. Implementing these ADTs using arrays (lists in Python) is straightforward, though for largescale
applications, circular buffers or linked lists may be more efficient for queues.
4. Understanding ADTs helps in choosing the right data structure for specific
problem requirements in software development.

ADITYA PANDEY 24/SWE/

10 10
 EXPERIMENT - 3
AIM: Write a program that reads an infix expression and converts the expression to postfix form. (Use
stack ADT).

THEORY:
In arithmetic expressions, infix notation is the standard way of writing operations where operators are
placed between operands (A + B). However, to evaluate expressions more easily, they are often
converted to postfix notation (Reverse Polish Notation), where operators are written after the operands
(A B +). Postfix expressions eliminate the need for parentheses and operator precedence rules.

Steps for Infix to Postfix Conversion:

Operands are added directly to the output.
Operators are pushed to the stack, but if an operator with lower or equal precedence is already on
top of the stack, we pop operators from the stack to the output until this condition no longer holds.
Parentheses:
● Left parenthesis is pushed onto the stack.
● Right parenthesis causes operators to be popped from the stack to the output until a left
parenthesis ( is encountered. The left parenthesis is then discarded.

SOURCE CODE:
#include <iostream>
#include <stack>
#include <string>
#include <cctype>

using namespace std;

int precedence(char op) {

if (op == '+' || op == '-') return 1;
else if (op == '*' || op == '/') return 2;
else if (op == '^') return 3;
return 0;
}

bool isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}

string infixToPostfix(const string& infix) {

stack<char> s;
string postfix;

for (char c : infix) {

if (isspace(c)) continue;

if (isalnum(c)) {
postfix += c;
}
ADITYA PANDEY 24/SWE/
11 10
 else if (c == '(') {
s.push(c);
}
else if (c == ')') {
while (!s.empty() && s.top() != '(') {
postfix += ' ';
postfix += s.top();
s.pop();
}
s.pop();
}
else if (isOperator(c)) {
postfix += ' ';
while (!s.empty() && precedence(s.top()) >= precedence(c)) {
postfix += s.top();
s.pop();
postfix += ' ';
}
s.push(c);
}
}

while (!s.empty()) {
postfix += ' ';
postfix += s.top();
s.pop();
}

return postfix;
}

int main() {
cout << "Name: ADITYA PANDEY\nRoll NO.: 24/SWE/10\n" << endl;
string infix;

cout << "Enter an infix expression: ";

getline(cin, infix);

string postfix = infixToPostfix(infix);

cout << "Postfix expression: " << postfix << endl;

return 0;
}

ADITYA PANDEY 24/SWE/

12 10
OUTPUT:

LEARNINGS:

1. Infix to Postfix Conversion simplifies expression evaluation as postfix expressions do

not require parentheses.
2. The Stack ADT is essential for handling operator precedence and parentheses efficiently.
3. Operator Precedence and Associativity are fundamental in infix-to-postfix conversion.
Higher precedence operators are applied before lower precedence ones, and associativity
rules dictate the order for operators of the same precedence.
4. Understanding postfix notation and stack-based algorithms is valuable in compiler
design and expression evaluation in programming.

ADITYA PANDEY 24/SWE/

13 10
 EXPERIMENT - 4
AIM: Write a program to implement the following using a singly linked list. a) Stack ADT b) Queue
ADT

THEORY:

Singly Linked List:

A singly linked list is a data structure consisting of nodes where each node contains data and a pointer
(or reference) to the next node in the sequence. Unlike arrays, linked lists don’t have a fixed size and
allow dynamic memory allocation, making them ideal for implementing dynamic data structures like
stacks and queues.

STACK:
A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that
the last element added to the stack is the first one to be removed. Think of a stack of plates – you add
new plates on top, and you take plates from the top.

Operations on Stack
Push: Add an element to the top of the stack.
Pop: Remove the element from the top of the stack.
Peek (or Top): Retrieve the element at the top of the stack without removing it.
isEmpty: Check if the stack is empty.
isFull: Check if the stack is full (only relevant for a fixed-size stack implemented using an array).

QUEUE:
A Queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that
the first element added to the queue is the first one to be removed. A queue is similar to a line of
people; people join from the back and leave from the front.

Operations on Queue
Enqueue: Add an element to the end (rear) of the queue.
Dequeue: Remove an element from the front of the queue.
Front: Retrieve the element at the front without removing
it. isEmpty: Check if the queue is empty.
isFull: Check if the queue is full (only relevant for a fixed-size queue implemented using an array).

SOURCE CODE:
#include <iostream>
using namespace std;

struct Node {
int data;
Node* next;
ADITYA PANDEY 24/SWE/
14 10
 Node(int value) : data(value), next(nullptr) {}
};

// Stack ADT using singly linked list

class Stack {
private:
Node* top;

public:
Stack() : top(nullptr) {}

void push(int value) {

Node* newNode = new Node(value);
newNode->next = top;
top = newNode;
cout << value << " pushed to stack." << endl;
}

int pop() {
if (isEmpty()) {
cout << "Stack is empty." << endl;
return -1; // Indicate empty stack
}
Node* temp = top;
int poppedValue = top->data;
top = top->next;
delete temp;
cout << poppedValue << " popped from stack." << endl;
return poppedValue;
}

int peek() {
if (isEmpty()) {
cout << "Stack is empty." << endl;
return -1; // Indicate empty stack
}
return top->data;
}

bool isEmpty() {
return top == nullptr;
}
};

// Queue ADT using singly linked list

class Queue {
private:
Node* front;
Node* rear;

public:
Queue() : front(nullptr), rear(nullptr) {}

void enqueue(int value) {

Node* newNode = new Node(value);
if (rear) {
rear->next = newNode;
} else {
front = newNode; // Queue was empty
}
rear = newNode;
ADITYA PANDEY 24/SWE/
15 10
 cout << value << " enqueued to queue." << endl;
}

int dequeue() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return -1; // Indicate empty queue
}
Node* temp = front;
int dequeuedValue = front->data;
front = front->next;
if (!front) rear = nullptr; // Queue is now empty
delete temp;
cout << dequeuedValue << " dequeued from queue." << endl;
return dequeuedValue;
}

int peek() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return -1; // Indicate empty queue
}
return front->data;
}

bool isEmpty() {
return front == nullptr;
}
};

int main() {
cout << "Name: ADITYA PANDEY\nRoll NO.: 24/SWE/10\n" << endl;
Stack stack;
Queue queue;
int choice, value;

while (true) {
cout << "\nChoose an operation:\n";
cout << "1. Push to Stack\n";
cout << "2. Pop from Stack\n";
cout << "3. Peek Stack\n";
cout << "4. Enqueue to Queue\n";
cout << "5. Dequeue from Queue\n";
cout << "6. Peek Queue\n";
cout << "0. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to push onto the stack: ";
cin >> value;
stack.push(value);
break;
case 2:
stack.pop();
break;
case 3:
cout << "Top element: " << stack.peek() << endl;
break;
case 4:
ADITYA PANDEY 24/SWE/
16 10
 cout << "Enter value to enqueue to the queue: ";
cin >> value;
queue.enqueue(value);
break;
case 5:
queue.dequeue();
break;
case 6:
cout << "Front element: " << queue.peek() << endl;
break;
case 0:
cout << "Exiting program.\n";
return 0;
default:
cout << "Invalid choice. Try again.\n";
}
}

return 0;
}

OUTPUT:

LEARNINGS:
1. Stack ADT using linked lists is efficient in terms of memory, as it dynamically grows
and shrinks, making it suitable for applications requiring LIFO access.
2. Queue ADT using linked lists also benefits from dynamic memory allocation and is
efficient for FIFO access, useful for tasks like scheduling and buffering.
3. Using Linked Lists to implement these ADTs provides flexibility and overcomes
the limitations of static array sizes.
4. Understanding linked lists in data structure implementation enhances efficiency and
memory management, which is crucial in system-level programming and application
development.

ADITYA PANDEY 24/SWE/

17 10
 EXPERIMENT - 5
AIM: Write a program to perform the following operations:
a) Construct and insert elements into binary search tree.
b) Search for a key element in the above binary search tree.
c) Delete an element from the above binary search tree.

THEORY:

Binary Search Tree (BST):

A Binary Search Tree (BST) is a binary tree data structure with the following
properties: Each node has a key and up to two children (left and right).
Left Child: Contains values less than the node’s key.
Right Child: Contains values greater than the node’s
key.

This structure enables efficient search, insertion, and deletion operations, making it useful for
applications that require dynamic data management.

Benefits of Using a BST:

Efficient Searching and Updating: Operations like search, insert, and delete are on average O(logn),
making BSTs efficient for dynamic datasets.
Sorted Structure: In-order traversal of a BST yields elements in sorted order, which is useful in
applications like databases and searching algorithms.

SOURCE CODE:
#include <iostream>
using namespace std;

struct Node {
int data;
Node* left;
Node* right;
Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

class BST {
ADITYA PANDEY 24/SWE/
18 10
private:
Node* root;

Node* insert(Node* node, int value) {

if (!node) return new Node(value);
if (value < node->data) node->left = insert(node->left, value);
else if (value > node->data) node->right = insert(node->right, value);
return node;
}

Node* search(Node* node, int key) {

if (!node || node->data == key) return node;
if (key < node->data) return search(node->left, key);
else return search(node->right, key);
}

Node* findMin(Node* node) {

while (node && node->left) {
node = node->left;
}
return node;
}

Node* deleteNode(Node* node, int key) {

if (!node) return node;

if (key < node->data) node->left = deleteNode(node->left, key);

else if (key > node->data) node->right = deleteNode(node->right, key);
else { // Node with only one child or no child
if (!node->left) {
Node* temp = node->right;
delete node;
return temp;
} else if (!node->right) {
Node* temp = node->left;
delete node;
return temp;
}
// Node with two children: get the inorder successor
Node* temp = findMin(node->right);
node->data = temp->data; // Copy the inorder successor's content to this node
node->right = deleteNode(node->right, temp->data); // Delete the inorder successor
}
return node;
}

void inorder(Node* node) {

if (node) {
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
}

public:
BST() : root(nullptr) {}

void insert(int value) {

root = insert(root, value);
cout << value << " inserted into the BST." << endl;
}
ADITYA PANDEY 24/SWE/
19 10
 bool search(int key) {
Node* result = search(root, key);
return result != nullptr; // Returns true if found
}

void deleteNode(int key) {

root = deleteNode(root, key);
cout << key << " deleted from the BST." << endl;
}

void inorderTraversal() {
cout << "Inorder traversal of the BST: ";
inorder(root);
cout << endl;
}
};

int main() {
cout << "Name: ADITYA PANDEY\nRoll NO.: 24/SWE/10\n" << endl;
BST bst;
int choice, value;
cout << "\nChoose an operation:\n";
cout << "1. Insert into BST\n";
cout << "2. Search in BST\n";
cout << "3. Delete from BST\n";
cout << "4. Display Inorder Traversal\n";
cout << "0. Exit\n";
while (true) {

cout << "Enter your choice: ";

cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to insert into the BST: ";
cin >> value;
bst.insert(value);
break;
case 2:
cout << "Enter value to search in the BST: ";
cin >> value;
cout << (bst.search(value) ? "Key " + to_string(value) + " found in the BST." : "Key " + to_string(value) + " not
found in the BST.") << endl;
break;
case 3:
cout << "Enter value to delete from the BST: ";
cin >> value;
bst.deleteNode(value);
break;
case 4:
bst.inorderTraversal();
break;
case 0:
cout << "Exiting program.\n";
return 0;
default:
cout << "Invalid choice. Try again.\n";
}
}

ADITYA PANDEY 24/SWE/

20 10
 return 0;
}

OUTPUT:

LEARNINGS:
1. Binary Search Trees (BST) provide an efficient structure for ordered data, enabling O(log
n) time complexity for search, insert, and delete operations in balanced cases.
2. In-order traversal of a BST retrieves elements in sorted order.
3. Search Operation in a BST starts from the root and traverses either left or right
depending on the key value, making it efficient for ordered data.

ADITYA PANDEY 24/SWE/

21 10
 EXPERIMENT - 6
AIM: Write a program to implement all the functions of a dictionary (ADT) using Hashing.

THEORY:
Dictionary ADT:
A Dictionary Abstract Data Type (ADT) is a collection of key-value pairs where each key is unique.
The dictionary allows for efficient insertion, deletion, and lookup operations. Hashing is a technique
used to implement dictionary ADT due to its efficient data retrieval capability.

Hashing for Dictionary ADT:

Hashing is a method of mapping data to a specific location (or index) in a data structure, such as an
array, using a hash function. This allows constant time complexity, O(1), on average for insertion,
search, and deletion operations.

Operations in a Dictionary ADT using Hashing:

Insertion: Use the hash function to find an index and insert the key-value pair at that location. Handle
collisions if they occur.
Search: Use the hash function to locate the key. If the key is found at the computed index, return the
value; otherwise, handle the collision as needed.
Deletion: Locate the key using the hash function. If found, remove the key-value pair and handle any
empty spots left by the deletion to avoid search issues.

SOURCE CODE:

#include <iostream>
#include <list>
#include <string>
using namespace std;

struct DictionaryEntry {
string key;
string value;
};

class HashTable {
private:
static const int hashSize = 10; // Size of the hash table
list<DictionaryEntry> table[hashSize]; // Hash table using separate chaining

// Hash function to compute the index

int hashFunction(const string& key) {
int hash = 0;
for (char ch : key) {
hash += ch; // Simple sum of ASCII values
}
return hash % hashSize;

ADITYA PANDEY 24/SWE/

22 10
 }

public:
// Insert a key-value pair into the dictionary
void insert(const string& key, const string& value) {
int index = hashFunction(key);
// Check if the key already exists and update the value if it does
for (auto& entry : table[index]) {
if (entry.key == key) {
entry.value = value; // Update existing value
return;
}
}
// If key does not exist, insert a new entry
table[index].push_back({key, value});
cout << "Inserted (" << key << ", " << value << ") into the dictionary." << endl;
}

string search(const string& key) {

int index = hashFunction(key);
for (const auto& entry : table[index]) {
if (entry.key == key) {
return entry.value; // Return the found value
}
}
return ""; // Key not found
}

void del(const string& key) {

int index = hashFunction(key);
auto& entries = table[index];
for (auto it = entries.begin(); it != entries.end(); ++it) {
if (it->key == key) {
entries.erase(it);
cout << "Deleted entry with key: " << key << endl;
return;
}
}
cout << "Key not found: " << key << endl;
}

void display() {
cout << "Dictionary contents:" << endl;
for (int i = 0; i < hashSize; i++) {
if (!table[i].empty()) {
for (const auto& entry : table[i]) {
cout << "Key: " << entry.key << ", Value: " << entry.value << endl;
}
}
}
}
};

int main() {
cout << "Name: ADITYA PANDEY\nRoll NO.: 24/SWE/10\n" << endl;
HashTable dictionary;
ADITYA PANDEY 24/SWE/
23 10
 int choice;
string key, value;
cout << "\nChoose an operation:\n";
cout << "1. Insert a key-value pair\n";
cout << "2. Search for a key\n";
cout << "3. Delete a key\n";
cout << "4. Display dictionary contents\n";
cout << "0. Exit\n";
while (true) {

cout << "Enter your choice: ";

cin >> choice;

switch (choice) {
case 1:
cout << "Enter key to insert: ";
cin >> key;
cout << "Enter value for " << key << ": ";
cin.ignore();
getline(cin, value);
dictionary.insert(key, value);
break;
case 2:
cout << "Enter key to search: ";
cin >> key;
value = dictionary.search(key);
if (!value.empty()) {
cout << "Value for key '" << key << "': " << value << endl;
} else {
cout << "Key not found: " << key << endl;
}
break;
case 3:
cout << "Enter key to delete: ";
cin >> key;
dictionary.del(key);
break;
case 4:
dictionary.display();
break;
case 0:
cout << "Exiting program.\n";
return 0;
default:
cout << "Invalid choice. Try again.\n";
}
}

return 0;
}

ADITYA PANDEY 24/SWE/

24 10
OUTPUT:

LEARNINGS:
1. Hash Tables provide efficient key-value storage, allowing constant time average-
case complexity for insert, search, and delete operations.
2. Hash Functions are crucial to mapping keys to table indices. Choosing a good hash
function minimizes collisions, improving the efficiency of the hash table.
3. Collision Handling with Chaining allows multiple elements to occupy the same index,
with each index containing a list of key-value pairs.
4. Understanding hash tables is essential for implementing dictionaries and optimizing
data retrieval, which are foundational in database indexing and memory management.

ADITYA PANDEY 24/SWE/

25 10
 EXPERIMENT - 7
AIM: Write a program that use recursive and non-recursive functions to traverse the given binary tree
in a) Preorder b) Inorder c) Postorder

THEORY:
In a binary tree, each node has at most two children, called the left and right child. Traversing a binary
tree involves visiting each node in a specific order, and the main traversal methods are Preorder,
Inorder, and Postorder.

Inorder Traversal:
Inorder traversal visits the node in the order: Left -> Root -> Right

Preorder Traversal:
Preorder traversal visits the node in the order: Root -> Left -> Right

Postorder Traversal:
Postorder traversal visits the node in the order: Left -> Right -> Root

SOURCE CODE:
#include <iostream>
#include <stack>
using namespace std;

struct Node {
int data;
Node* left;
Node* right;
Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

class BinaryTree {
public:
Node* root;

BinaryTree() : root(nullptr) {}

void recursivePreorder(Node* node) {

if (node) {
cout << node->data << " ";
recursivePreorder(node->left);
recursivePreorder(node->right);
}
}

void iterativePreorder() {
if (!root) return;

ADITYA PANDEY 24/SWE/

26 10
 stack<Node*> stack;
stack.push(root);

while (!stack.empty()) {
Node* node = stack.top();
stack.pop();
cout << node->data << " ";

if (node->right) stack.push(node->right);
if (node->left) stack.push(node->left);
}
}

void recursiveInorder(Node* node) {

if (node) {
recursiveInorder(node->left);
cout << node->data << " ";
recursiveInorder(node->right);
}
}

void iterativeInorder() {
stack<Node*> stack;
Node* current = root;

while (current || !stack.empty()) {

while (current) {
stack.push(current);
current = current->left;
}

current = stack.top();
stack.pop();
cout << current->data << " ";
current = current->right;
}
}

void recursivePostorder(Node* node) {

if (node) {
recursivePostorder(node->left);
recursivePostorder(node->right);
cout << node->data << " ";
}
}

void iterativePostorder() {
if (!root) return;

stack<Node*> stack1, stack2;

stack1.push(root);

ADITYA PANDEY 24/SWE/

27 10
 while (!stack1.empty()) {
Node* node = stack1.top();
stack1.pop();
stack2.push(node);

if (node->left) stack1.push(node->left);
if (node->right) stack1.push(node->right);
}

while (!stack2.empty()) {
cout << stack2.top()->data << " ";
stack2.pop();
}
}

void insert(int value) {

if (!root) {
root = new Node(value);
} else {
insertRecursively(root, value);
}
}

void insertRecursively(Node* node, int value) {

if (value < node->data) {
if (node->left) {
insertRecursively(node->left, value);
} else {
node->left = new Node(value);
}
} else {
if (node->right) {
insertRecursively(node->right, value);
} else {
node->right = new Node(value);
}
}
}

void preorderTraversal() {
cout << "Preorder (Recursive): ";
recursivePreorder(root);
cout << endl;

cout << "Preorder (Iterative): ";

iterativePreorder();
cout << endl;
}

void inorderTraversal() {
cout << "Inorder (Recursive): ";
recursiveInorder(root);
ADITYA PANDEY 24/SWE/
28 10
 cout << endl;

cout << "Inorder (Iterative): ";

iterativeInorder();
cout << endl;
}

void postorderTraversal() {
cout << "Postorder (Recursive): ";
recursivePostorder(root);
cout << endl;

cout << "Postorder (Iterative): ";

iterativePostorder();
cout << endl;
}
};

int main() {
cout << "Name: ADITYA PANDEY\nRoll NO.: 24/SWE/10\n" << endl;
BinaryTree tree;
int choice, value;
cout << "\nChoose an operation:\n";
cout << "1. Insert a node\n";
cout << "2. Display Preorder traversal\n";
cout << "3. Display Inorder traversal\n";
cout << "4. Display Postorder traversal\n";
cout << "0. Exit\n";
while (true) {

cout << "Enter your choice: ";

cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to insert: ";
cin >> value;
tree.insert(value);
cout << value << " inserted into the binary tree.\n";
break;
case 2:
tree.preorderTraversal();
break;
case 3:
tree.inorderTraversal();
break;
case 4:
tree.postorderTraversal();
break;
case 0:
cout << "Exiting program.\n";
return 0;
ADITYA PANDEY 24/SWE/
29 10
 default:
cout << "Invalid choice. Try again.\n";
}
}

return 0;
}
OUTPUT:

LEARNINGS:
1. Recursive traversals provide an intuitive approach to tree operations, while non-recursive
traversals offer more control over memory usage.
2. Non-Recursive Traversals simulate recursion using explicit stacks, which can handle
large trees more efficiently in terms of memory, as they avoid potential stack overflow
issues.
3. Preorder Traversal is useful when the root node needs to be processed first, Inorder
Traversal is ideal for sorting (especially in binary search trees), and Postorder Traversal is
useful when child nodes need to be processed before the parent.

ADITYA PANDEY 24/SWE/

30 10
 EXPERIMENT - 8
AIM: Write a program for the implementation of BFS and DFS for a graph.

THEORY:

Graph: A graph is a collection of nodes (vertices) and edges connecting pairs of nodes. Graphs can be
represented in various ways, the most common being:

Adjacency Matrix: A 2D array where the cell at (i, j) indicates the presence or absence of an edge
between vertex i and vertex j.
Adjacency List: A collection of lists where each list corresponds to a vertex and contains the vertices
that are adjacent to it.

Breadth-First Search (BFS): BFS is an algorithm for traversing or searching tree or graph data
structures. It starts at a selected node (source) and explores all its neighbors at the present depth before
moving on to nodes at the next depth level.

Depth-First Search (DFS): DFS is another algorithm for traversing or searching through a graph. It
starts at a root node and explores as far as possible along each branch before backtracking.

SOURCE CODE:
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

class Graph {
private:
int vertices;
list<int>* adjList;

public:
Graph(int V) {
vertices = V;
adjList = new list<int>[V];
}

~Graph() {
delete[] adjList;
}

void addEdge(int v, int w) {

adjList[v].push_back(w);
adjList[w].push_back(v);
}
ADITYA PANDEY 24/SWE/
31 10
 void BFS(int start) {
vector<bool> visited(vertices, false);
queue<int> q;
visited[start] = true;
q.push(start);

cout << "BFS starting from vertex " << start << ": ";
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current << " ";
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
cout << endl;
}

void DFSUtil(int v, vector<bool>& visited) {

visited[v] = true;
cout << v << " ";
for (int neighbor : adjList[v]) {
if (!visited[neighbor]) {
DFSUtil(neighbor, visited);
}
}
}

void DFS(int start) {

vector<bool> visited(vertices, false);
cout << "DFS starting from vertex " << start << ": ";
DFSUtil(start, visited);
cout << endl;
}
};

int main() {
cout << "Name: ADITYA PANDEY\nRoll NO.: 24/SWE/10\n" << endl;

int V, choice, v, w;
cout << "Enter the number of vertices: ";
cin >> V;
Graph g(V);
cout << "\nMenu:\n";
cout << "1. Add an edge\n";
cout << "2. Perform BFS\n";
cout << "3. Perform DFS\n";
cout << "0. Exit\n";
ADITYA PANDEY 24/SWE/
32 10
 while (true) {

cout << "Enter your choice: ";

cin >> choice;

switch (choice) {
case 1:
cout << "Enter two vertices to add an edge between (v w): ";
cin >> v >> w;
if (v >= V || w >= V || v < 0 || w < 0) {
cout << "Invalid vertices. Try again.\n";
} else {
g.addEdge(v, w);
cout << "Edge added between " << v << " and " << w << ".\n";
}
break;
case 2:
cout << "Enter starting vertex for BFS: ";
cin >> v;
if (v >= V || v < 0) {
cout << "Invalid vertex. Try again.\n";
} else {
g.BFS(v);
}
break;
case 3:
cout << "Enter starting vertex for DFS: ";
cin >> v;
if (v >= V || v < 0) {
cout << "Invalid vertex. Try again.\n";
} else {
g.DFS(v);
}
break;
case 0:
cout << "Exiting program.\n";
return 0;
default:
cout << "Invalid choice. Try again.\n";
}
}

return 0;
}

ADITYA PANDEY 24/SWE/

33 10
OUTPUT:

LEARNINGS:

1. BFS (Breadth-First Search) is useful for exploring a graph level by level and is
commonly used to find the shortest path in unweighted graphs. BFS requires a queue data
structure to track the nodes to be visited.
2. DFS (Depth-First Search) explores the graph by diving deep into one branch before
backtracking. DFS can be implemented recursively or iteratively using a stack. Recursive
DFS utilizes the call stack, while iterative DFS explicitly uses a stack.
3. Analyzed the time and space complexity of both algorithms, understanding that both BFS and DFS
run in O(V + E) time, where V is the number of vertices and E This understanding aids in evaluating
the efficiency of algorithms.

ADITYA PANDEY 24/SWE/

34 10
 EXPERIMENT - 9
AIM: Write a program for implementation of following sorting methods: a) Bubble sort b) Insertion
sort c) Quick sort d) Merge sort e) Heap sort f) Radix sort g) Binary tree sort

THEORY:
Sorting algorithms are fundamental algorithms that arrange the elements of a list or array in a
particular order (usually ascending or descending).

1. Bubble Sort: A simple comparison-based sorting algorithm. It repeatedly steps through the list,
compares adjacent elements, and swaps them if they are in the wrong order. This process continues
until no swaps are needed.
Complexity: O(n^2) in the worst and average cases; O(n) in the best case

2. Insertion Sort: Builds a sorted array one element at a time. It takes each element from the unsorted
portion and inserts it into its correct position in the sorted portion of the array.
Complexity: O(n^2) in the worst and average cases; O(n) in the best case (when the array is already
sorted).

3. Quick Sort: A divide-and-conquer algorithm. It selects a 'pivot' element, partitions the other
elements into two sub-arrays according to whether they are less than or greater than the pivot, and
recursively sorts the sub-arrays.
Complexity: O(n log n) on average; O(n^2) in the worst case (when the pivot is the smallest or largest
element).

4. Merge Sort: Another divide-and-conquer algorithm. It divides the array into two halves,
recursively sorts both halves, and then merges them back together in sorted order.
Complexity: O(n log n) for all cases, making it more predictable than Quick Sort.

5. Heap Sort: Utilizes a binary heap data structure. It builds a max heap from the input data and
repeatedly extracts the maximum element from the heap to build the sorted array.
Complexity: O(n log n) for all cases, and it is an in-place sorting algorithm.

6. Radix Sort: A non-comparative sorting algorithm that sorts numbers by processing individual
digits. It sorts the input numbers by their least significant digit to the most significant digit using a
stable sub-sorting algorithm (like counting sort).
Complexity: O(nk), where n is the number of elements and k is the number of digits in the largest
number.

7. Binary Tree Sort: Involves inserting elements into a binary search tree (BST) and then performing
an in-order traversal of the tree to retrieve the sorted elements. This relies on the properties of BSTs,
where left children are smaller and right children are larger.
Complexity: O(n log n) on average for balanced trees; O(n^2) in the worst case for unbalanced trees.

ADITYA PANDEY 24/SWE/

35 10
SOURCE CODE:
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

// Bubble Sort
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}

// Insertion Sort
void insertionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

// Quick Sort
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
ADITYA PANDEY 24/SWE/
36 10
 }
}
swap(arr[i + 1], arr[high]);
return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {

if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

// Merge Sort
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(n1), R(n2);

for (int i = 0; i < n1; i++) L[i] = arr[left + i];

for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

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

void mergeSort(vector<int>& arr, int left, int right) {

if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
ADITYA PANDEY 24/SWE/
37 10
}

// Heap Sort
void heapify(vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

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

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

if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}

void heapSort(vector<int>& arr) {

int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}

// Radix Sort
void countingSort(vector<int>& arr, int exp) {
int n = arr.size();
vector<int> output(n);
int count[10] = {0};

for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;

for (int i = 1; i < 10; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) arr[i] = output[i];
}
ADITYA PANDEY 24/SWE/
38 10
void radixSort(vector<int>& arr) {
int maxVal = *max_element(arr.begin(), arr.end());
for (int exp = 1; maxVal / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}

// Binary Tree Sort

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode* insertTreeNode(TreeNode* root, int val) {

if (!root) return new TreeNode(val);
if (val < root->val) root->left = insertTreeNode(root->left, val);
else root->right = insertTreeNode(root->right, val);
return root;
}

void inorderTraversal(TreeNode* root, vector<int>& arr) {

if (!root) return;
inorderTraversal(root->left, arr);
arr.push_back(root->val);
inorderTraversal(root->right, arr);
}

void binaryTreeSort(vector<int>& arr) {

TreeNode* root = nullptr;
for (int val : arr) root = insertTreeNode(root, val);
arr.clear();
inorderTraversal(root, arr);
}

int main() {
string name;
string rollNo;
vector<int> arr;

ADITYA PANDEY 24/SWE/

39 10
int n;
cout << "Enter the number of elements in the array: ";
cin >> n;

cout << "Enter " << n << " integers: ";

for (int i = 0; i < n; i++) {
int value;
cin >> value;
arr.push_back(value);
}

// Print user information

cout << "\nName: " << "ADITYA PANDEY" << endl;
cout << "Roll No.: " << "24/SWE/10" << endl;

// Perform sorting using different algorithms

vector<int> arr1 = arr;
bubbleSort(arr1);
cout << "Bubble Sort: ";
for (int num : arr1) cout << num << " ";
cout << endl;

vector<int> arr2 = arr;

insertionSort(arr2);
cout << "Insertion Sort: ";
for (int num : arr2) cout << num << " ";
cout << endl;

vector<int> arr3 = arr;

quickSort(arr3, 0, arr3.size() - 1);
cout << "Quick Sort: ";
for (int num : arr3) cout << num << " ";
cout << endl;

vector<int> arr4 = arr;

mergeSort(arr4, 0, arr4.size() - 1);
cout << "Merge Sort: ";
for (int num : arr4) cout << num << " ";
cout << endl;

ADITYA PANDEY 24/SWE/

40 10
 vector<int> arr5 = arr;
heapSort(arr5);
cout << "Heap Sort: ";
for (int num : arr5) cout << num << " ";
cout << endl;

vector<int> arr6 = arr;

radixSort(arr6);
cout << "Radix Sort: ";
for (int num : arr6) cout << num << " ";
cout << endl;

vector<int> arr7 = arr;

binaryTreeSort(arr7);
cout << "Binary Tree Sort: ";
for (int num : arr7) cout << num << " ";
cout << endl;

return 0;
}
OUTPUT:

ADITYA PANDEY 24/SWE/

41 10
LEARNINGS:

1. Bubble Sort is straightforward but inefficient for large lists.

2. Insertion Sort works well on small or partially sorted data.
3. Quick Sort is efficient on average but requires careful handling of pivot selection.
4. Merge Sort is stable and efficient but requires extra space.
5. Heap Sort provides \(O(n \log n)\) time without additional memory.
6. Radix Sort is ideal for integer sorting without comparisons.
7. Binary Tree Sort offers an alternative sorting method based on tree traversal.

ADITYA PANDEY 24/SWE/

42 10
 EXPERIMENT - 10
AIM: Write a program to perform the following operations:
(a)Insertion into a B-tree (b) Searching in a B-tree (c) Delete an element from a B-tree.

THEORY:

B-Tree: A B-tree is a self-balancing tree data structure that maintains sorted data and allows for
efficient insertion, deletion, and search operations. It is designed to work well on disk storage systems,
making it suitable for databases and filesystems.

Node Structure: Each node can contain multiple keys and child pointers. A B-tree of order 𝑚 can
B-trees are characterized by the following properties:

have a maximum of m−1 keys and m children.

Balanced Tree: All leaf nodes are at the same depth, ensuring balanced access times for search
operations.
Minimum Degree (t): Each node (except the root) must contain at
least t−1 keys and can contain at most m−1 keys (where m =2t).
Dynamic Growth: Nodes can split when they exceed their maximum capacity, ensuring that the tree
remains balanced.

SOURCE CODE:
#include <iostream>
using namespace std;

class BTreeNode {
int *keys; // Array of keys in the node
int t; // Minimum degree (defines the range for the number of keys)
BTreeNode **C; // Array of child pointers
int n; // Current number of keys
bool leaf; // True if leaf node

public:
BTreeNode(int _t, bool _leaf);

// Insert a new key in the subtree rooted with this node

void insertNonFull(int k);

// Split the child y of this node. i is index of y in child array C[].

void splitChild(int i, BTreeNode *y);

// Find a key in the subtree rooted with this node

BTreeNode *search(int k);

// Remove a key from the subtree rooted with this node

void remove(int k);

// Remove from leaf node

void removeFromLeaf(int idx);

// Remove from non-leaf node

void removeFromNonLeaf(int idx);

ADITYA PANDEY 24/SWE/

43 10
 // Get the predecessor of the key at idx
int getPred(int idx);

// Get the successor of the key at idx

int getSucc(int idx);

// Fill the child C[idx] which has less than t-1 keys
void fill(int idx);

// Borrow a key from the previous child

void borrowFromPrev(int idx);

// Borrow a key from the next child

void borrowFromNext(int idx);

// Merge C[idx] with C[idx+1]

void merge(int idx);

// Display the B-tree

void traverse();

friend class BTree;

};

class BTree {
BTreeNode *root; // Pointer to root node
int t; // Minimum degree

public:
BTree(int _t) { root = nullptr; t = _t; }

void traverse() {
if (root != nullptr) root->traverse();
}

BTreeNode* search(int k) {
return (root == nullptr) ? nullptr : root->search(k);
}

void insert(int k);

void remove(int k);
};

// B-tree node constructor

BTreeNode::BTreeNode(int t1, bool leaf1) {
t = t1;
leaf = leaf1;
keys = new int[2 * t - 1];
C = new BTreeNode *[2 * t];
n = 0;
}

// Traverse all nodes in the B-tree

void BTreeNode::traverse() {
for (int i = 0; i < n; i++) {
if (!leaf) C[i]->traverse();
cout << " " << keys[i];
}
if (!leaf) C[n]->traverse();
}

ADITYA PANDEY 24/SWE/

44 10
// Search a key in the subtree rooted with this node
BTreeNode *BTreeNode::search(int k) {
int i = 0;
while (i < n && k > keys[i]) i++;
if (keys[i] == k) return this;
if (leaf) return nullptr;
return C[i]->search(k);
}

// Insert a key into the B-tree

void BTree::insert(int k) {
if (root == nullptr) {
root = new BTreeNode(t, true);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2 * t - 1) {
BTreeNode *s = new BTreeNode(t, false);
s->C[0] = root;
s->splitChild(0, root);
int i = (s->keys[0] < k) ? 1 : 0;
s->C[i]->insertNonFull(k);
root = s;
} else {
root->insertNonFull(k);
}
}
}

void BTreeNode::insertNonFull(int k) {
int i = n - 1;
if (leaf) {
while (i >= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = k;
n = n + 1;
} else {
while (i >= 0 && keys[i] > k) i--;
if (C[i + 1]->n == 2 * t - 1) {
splitChild(i + 1, C[i + 1]);
if (keys[i + 1] < k) i++;
}
C[i + 1]->insertNonFull(k);
}
}

// Split the child y of this node

void BTreeNode::splitChild(int i, BTreeNode *y) {
BTreeNode *z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t - 1; j++) z->keys[j] = y->keys[j + t];
if (!y->leaf) {
for (int j = 0; j < t; j++) z->C[j] = y->C[j + t];
}
y->n = t - 1;
for (int j = n; j >= i + 1; j--) C[j + 1] = C[j];
C[i + 1] = z;
for (int j = n - 1; j >= i; j--) keys[j + 1] = keys[j];
keys[i] = y->keys[t - 1];
ADITYA PANDEY 24/SWE/
45 10
 n = n + 1;
}

// Remove a key from the B-tree

void BTree::remove(int k) {
if (!root) {
cout << "The tree is empty\n";
return;
}
root->remove(k);
if (root->n == 0) {
BTreeNode *tmp = root;
root = (root->leaf) ? nullptr : root->C[0];
delete tmp;
}
}

// Remove function definitions in BTreeNode class

void BTreeNode::remove(int k) {
int idx = 0;
while (idx < n && keys[idx] < k) idx++;
if (idx < n && keys[idx] == k) {
if (leaf) removeFromLeaf(idx);
else removeFromNonLeaf(idx);
} else {
if (leaf) {
cout << "The key " << k << " is not in the tree\n";
return;
}
bool flag = (idx == n);
if (C[idx]->n < t) fill(idx);
if (flag && idx > n) C[idx - 1]->remove(k);
else C[idx]->remove(k);
}
}

void BTreeNode::removeFromLeaf(int idx) {

for (int i = idx + 1; i < n; ++i)
keys[i - 1] = keys[i];
n--;
}

void BTreeNode::removeFromNonLeaf(int idx) {

int k = keys[idx];
if (C[idx]->n >= t) {
int pred = getPred(idx);
keys[idx] = pred;
C[idx]->remove(pred);
} else if (C[idx + 1]->n >= t) {
int succ = getSucc(idx);
keys[idx] = succ;
C[idx + 1]->remove(succ);
} else {
merge(idx);
C[idx]->remove(k);
}
}

int BTreeNode::getPred(int idx) {

BTreeNode *cur = C[idx];
while (!cur->leaf) cur = cur->C[cur->n];
ADITYA PANDEY 24/SWE/
46 10
 return cur->keys[cur->n - 1];
}

int BTreeNode::getSucc(int idx) {

BTreeNode *cur = C[idx + 1];
while (!cur->leaf) cur = cur->C[0];
return cur->keys[0];
}

void BTreeNode::fill(int idx) {

if (idx != 0 && C[idx - 1]->n >= t) borrowFromPrev(idx);
else if (idx != n && C[idx + 1]->n >= t) borrowFromNext(idx);
else {
if (idx != n) merge(idx);
else merge(idx - 1);
}
}

void BTreeNode::borrowFromPrev(int idx) {

BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx - 1];
for (int i = child->n - 1; i >= 0; --i)
child->keys[i + 1] = child->keys[i];
if (!child->leaf) {
for (int i = child->n; i >= 0; --i)
child->C[i + 1] = child->C[i];
}
child->keys[0] = keys[idx - 1];
if (!child->leaf) child->C[0] = sibling->C[sibling->n];
keys[idx - 1] = sibling->keys[sibling->n - 1];
child->n += 1;
sibling->n -= 1;
}

void BTreeNode::borrowFromNext(int idx) {

BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx + 1];
child->keys[child->n] = keys[idx];
if (!child->leaf)
child->C[child->n + 1] = sibling->C[0];
keys[idx] = sibling->keys[0];
for (int i = 1; i < sibling->n; ++i)
sibling->keys[i - 1] = sibling->keys[i];
if (!sibling->leaf) {
for (int i = 1; i <= sibling->n; ++i)
sibling->C[i - 1] = sibling->C[i];
}
child->n += 1;
sibling->n -= 1;
}

void BTreeNode::merge(int idx) {

BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx + 1];
child->keys[t - 1] = keys[idx];
for (int i = 0; i < sibling->n; ++i)
child->keys[i + t] = sibling->keys[i];
if (!child->leaf) {
for (int i = 0; i <= sibling->n; ++i)
child->C[i + t] = sibling->C[i];
}
ADITYA PANDEY 24/SWE/
47 10
 for (int i = idx + 1; i < n; ++i)
keys[i - 1] = keys[i];
for (int i = idx + 2; i <= n; ++i)
C[i - 1] = C[i];
child->n += sibling->n + 1;
n--;
delete(sibling);
}

int main() {
cout << "Name: ADITYA PANDEY\nRoll NO.: 24/SWE/10\n" << endl;
BTree t(3); // A B-Tree with minimum degree 3

int n, val;
cout << "Enter the number of elements to insert: ";
cin >> n;
cout << "Enter " << n << " elements:\n";
for (int i = 0; i < n; i++) {
cin >> val;
t.insert(val);
}

cout << "Traversal of the B-tree: ";

t.traverse();
cout << endl;

cout << "Enter a key to search: ";

cin >> val;
if (t.search(val))
cout << "Element " << val << " is present in the B-tree.\n";
else
cout << "Element " << val << " is not present in the B-tree.\n";

cout << "Enter a key to remove: ";

cin >> val;
t.remove(val);
cout << "Traversal of the B-tree after deletion: ";
t.traverse();
cout << endl;

return 0;
}

OUTPUT:

ADITYA PANDEY 24/SWE/

48 10
LEARNINGS:
1. Insertion in B-trees ensures that the tree remains balanced by splitting nodes when necessary.
2. Searching in B-trees provides an efficient way to locate elements due to the ordered structure.
3. Deletion from B-trees requires careful handling to ensure balance and to avoid
underflow conditions in nodes.
4. B-trees are efficient for database indexing and filesystems due to their structure and
balanced nature, allowing fast access to large datasets.

ADITYA PANDEY 24/SWE/

49 10
 EXPERIMENT - 11
AIM: Write a program to perform the following operations:
a) Insert an element into a Min-Max heap.
b) Delete an element from a Min-Max heap.
c) Search for a key element in a Min-Max heap.

THEORY:

Min-Max Heap: A Min-Max heap is a specialized tree-based data structure that supports both
minimum and maximum heap properties.
It is a complete binary tree where:
Min Level: The nodes at even levels (starting from the root at level 0) maintain the min-heap property,
meaning that the value of each node is less than or equal to the values of its children.
Max Level: The nodes at odd levels maintain the max-heap property, meaning that the value of each
node is greater than or equal to the values of its children.
This structure allows efficient access to both the minimum and maximum elements, making it suitable
for applications requiring both operations.

SOURCE CODE:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class MinMaxHeap {
private:
vector<int> heap;

bool isMinLevel(int index) {

int level = 0;
while (index > 0) {
index = (index - 1) / 2;
level++;
}
return (level % 2 == 0);
}

void trickleUp(int index) {

// Move up to restore the min-max heap property
if (index == 0) return;
int parent = (index - 1) / 2;
if (isMinLevel(index)) {
if (heap[index] > heap[parent]) {
swap(heap[index], heap[parent]);
trickleUpMax(parent);
} else {
trickleUpMin(index);
ADITYA PANDEY 24/SWE/
50 10
 }
} else {
if (heap[index] < heap[parent]) {
swap(heap[index], heap[parent]);
trickleUpMin(parent);
} else {
trickleUpMax(index);
}
}
}

void trickleUpMin(int index) {

int grandparent = (index - 1) / 4;
if (grandparent >= 0 && heap[index] < heap[grandparent]) {
swap(heap[index], heap[grandparent]);
trickleUpMin(grandparent);
}
}

void trickleUpMax(int index) {

int grandparent = (index - 1) / 4;
if (grandparent >= 0 && heap[index] > heap[grandparent]) {
swap(heap[index], heap[grandparent]);
trickleUpMax(grandparent);
}
}

void trickleDown(int index) {

// Move down to restore the min-max heap property
if (isMinLevel(index)) trickleDownMin(index);
else trickleDownMax(index);
}

void trickleDownMin(int index) {

int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < heap.size() && heap[left] < heap[smallest]) smallest = left;
if (right < heap.size() && heap[right] < heap[smallest]) smallest = right;

if (smallest != index) {
swap(heap[index], heap[smallest]);
trickleDownMin(smallest);
}
}

void trickleDownMax(int index) {

int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < heap.size() && heap[left] > heap[largest]) largest = left;
ADITYA PANDEY 24/SWE/
51 10
 if (right < heap.size() && heap[right] > heap[largest]) largest = right;

if (largest != index) {
swap(heap[index], heap[largest]);
trickleDownMax(largest);
}
}

public:
void insert(int value) {
heap.push_back(value);
trickleUp(heap.size() - 1);
}

bool search(int key) {

for (int i = 0; i < heap.size(); i++) {
if (heap[i] == key) return true;
}
return false;
}

void deleteMin() {
if (heap.empty()) {
cout << "Heap is empty" << endl;
return;
}
heap[0] = heap.back();
heap.pop_back();
if (!heap.empty()) trickleDown(0);
}

void display() {
for (int val : heap) {
cout << val << " ";
}
cout << endl;
}
};

int main() {
cout << "Name: ADITYA PANDEY\nRoll NO.: 24/SWE/10\n" << endl;
MinMaxHeap heap;

int n, value, key;

// User input for insertion

cout << "Enter the number of elements to insert: ";
cin >> n;
cout << "Enter " << n << " elements:\n";
for (int i = 0; i < n; i++) {
cin >> value;
ADITYA PANDEY 24/SWE/
52 10
 heap.insert(value);
}

// Display heap after insertion

cout << "Heap elements after insertions: ";
heap.display();

// User input for searching

cout << "Enter a key to search: ";
cin >> key;
if (heap.search(key))
cout << "Element " << key << " found in the heap." << endl;
else
cout << "Element " << key << " not found in the heap." << endl;

// User input for deleting minimum

heap.deleteMin();
cout << "Heap elements after deleting the minimum: ";
heap.display();

return 0;
}
OUTPUT:

LEARNINGS:

1. Min-Max Heaps provide an efficient way to manage and retrieve both minimum
and maximum values.
2. The Min-Max Heap is useful for applications requiring frequent access to both the
minimum and maximum values.
3. Implementing Min-Max Heap operations requires careful handling of elements to
maintain the structure’s alternating min-max levels.

ADITYA PANDEY 24/SWE/

53 10
 EXPERIMENT - 12
AIM: Write a program to perform the following operations:
a) Insert an element into a AVL tree.
b) Delete an element from a AVL search tree.

THEORY:

AVL Tree: An AVL tree is a self-balancing binary search tree (BST) that maintains its balance
through height balancing. Named after its inventors Adelson-Velsky and Landis, an AVL tree ensures
that the heights of the two child subtrees of any node differ by no more than one. This property
guarantees logarithmic height, which leads to efficient operations.

Key Properties:
Balance Factor: For any node in the tree, the balance factor is defined as the height of the left
subtree minus the height of the right subtree. The balance factor can be -1, 0, or +1 for a balanced
AVL tree.
Self-Balancing: After insertions and deletions, the tree automatically rebalances itself through
rotations (single or double) to maintain the AVL property.

SOURCE CODE:
#include <iostream>
using namespace std;

class Node {
public:
int key;
Node* left;
Node* right;
int height;

Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}

};

int height(Node* N) {
return N ? N->height : 0;
}

int getBalance(Node* N) {
return N ? height(N->left) - height(N->right) : 0;
}

void updateHeight(Node* N) {
N->height = 1 + max(height(N->left), height(N->right));
}

Node* rightRotate(Node* y) {

ADITYA PANDEY 24/SWE/

54 10
 Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;

updateHeight(y);
updateHeight(x);
return x;
}

Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
updateHeight(x);
updateHeight(y);
return y;
}

Node* insert(Node* node, int key) {

if (!node) return new Node(key);

if (key < node->key)

node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;

updateHeight(node);
int balance = getBalance(node);

// Perform rotations to balance the tree

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

Node* minValueNode(Node* node) {

Node* current = node;
ADITYA PANDEY 24/SWE/
55 10
 while (current->left)
current = current->left;
return current;
}

Node* deleteNode(Node* root, int key) {

if (!root) return root;

if (key < root->key)

root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
if (!root->left || !root->right) {
Node* temp = root->left ? root->left : root->right;
if (!temp) {
temp = root;
root = nullptr;
} else
*root = *temp;
delete temp;
} else {
Node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}

if (!root) return root;

updateHeight(root);
int balance = getBalance(root);

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

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

void inOrder(Node* root) {

if (root) {
inOrder(root->left);
ADITYA PANDEY 24/SWE/
56 10
 cout << root->key << " ";
inOrder(root->right);
}
}

int main() {
cout << "Name: Aditya Pandey\nRoll NO.: 24/SWE/10\n" << endl;

Node* root = nullptr;

int choice, value;
cout << "\nAVL Tree Operations Menu:\n";
cout << "1. Insert a node\n";
cout << "2. Delete a node\n";
cout << "3. In-order Traversal\n";
cout << "4. Exit\n";
do {

cout << "Enter your choice: ";

cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to insert: ";
cin >> value;
root = insert(root, value);
cout << "Node inserted successfully." << endl;
break;
case 2:
cout << "Enter value to delete: ";
cin >> value;
root = deleteNode(root, value);
cout << "Node deleted successfully." << endl;
break;
case 3:
cout << "In-order traversal of the AVL tree: ";
inOrder(root);
cout << endl;
break;
case 4:
cout << "Exiting program.\n";
break;
default:
cout << "Invalid choice. Please try again." << endl;
}

} while (choice != 4);

return 0;
}

ADITYA PANDEY 24/SWE/

57 10
OUTPUT:

LEARNINGS:
1. AVL Trees maintain balance by performing rotations after insertions and deletions,
ensuring O(log n) time complexity for these operations.
2. The balance factor helps in determining the type of rotation needed to maintain the
AVL property.
3. Implementing AVL Tree operations requires careful handling of node heights
and rebalancing conditions.

ADITYA PANDEY 24/SWE/

58 10