Q1. 1D array – implimentation.

#include <iostream>

using namespace std;

int main() {

int array[5] = {10, 20, 30, 40, 50};

cout << "Initial Array: ";

for (int i = 0; i < 5; i++) {

cout << array[i] << " ";

cout << endl;

cout << "Element at index 0: " << array[0] << endl; // Accessing first element

cout << "Element at index 3: " << array[3] << endl; // Accessing fourth element

array[2] = 100; // Modify element at index 2

cout << "Array after modification: ";

for (int i = 0; i < 5; i++) {

cout << array[i] << " ";

cout << endl;

int newArray[6] = {10, 20, 30, 40, 50, 60}; // Adding an element (we increase the array size
manually)

cout << "Array after adding 60: ";

for (int i = 0; i < 6; i++) {

cout << newArray[i] << " ";

cout << end

int insertIndex = 1;

int insertValue = 15;

int tempArray[7]; // New array with extra space for insertion

for (int i = 0; i < insertIndex; i++) {

tempArray[i] = newArray[i];

tempArray[insertIndex] = insertValue;

for (int i = insertIndex; i < 6; i++) {

tempArray[i + 1] = newArray[i];

cout << "Array after inserting 15 at index 1: ";

for (int i = 0; i < 7; i++) {

cout << tempArray[i] << " ";

cout << endl;

int removeIndex = 2;

int newSize = 6;

int removedArray[6]; // Array after removing an element

for (int i = 0; i < removeIndex; i++) {

removedArray[i] = tempArray[i];

for (int i = removeIndex + 1; i < 7; i++) {

removedArray[i - 1] = tempArray[i];

}
 cout << "Array after removing the element at index 2: ";

for (int i = 0; i < newSize; i++) {

cout << removedArray[i] << " ";

cout << endl;

cout << "Length of the array: " << 6 << endl; // The size of the array is fixed here (6
elements)

return 0;

OUTPUT

Q 2. MATRIX ADDITION

#include <iostream>

using namespace std;

int main() {

int m, n
cout << "Enter the number of rows (m): ";

cin >> m;

cout << "Enter the number of columns (n): ";

cin >> n;

int matrix1[m][n], matrix2[m][n], result[m][n];

cout << "Enter elements of the first matrix:\n";

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

cout << "Enter element (" << i + 1 << "," << j + 1 << "): ";

cin >> matrix1[i][j];

cout << "Enter elements of the second matrix:\n";

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

cout << "Enter element (" << i + 1 << "," << j + 1 << "): ";

cin >> matrix2[i][j];

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

result[i][j] = matrix1[i][j] + matrix2[i][j];

cout << "Resultant matrix after addition:\n";

for (int i = 0; i < m; i++) {

 for (int j = 0; j < n; j++) {

cout << result[i][j] << " ";

cout << endl;

return 0;

OUTPUT

Q 3. Matrix multiplication

#include <iostream>

using namespace std;

int main() {

int m, n, p, q;

cout << "Enter the number of rows and columns for the first matrix (m x n): ";

cin >> m >> n;

cout << "Enter the number of rows and columns for the second matrix (p x q): ";

cin >> p >> q;

if (n != p) {

cout << "Matrix multiplication not possible. Columns of the first matrix must be equal
to rows of the second matrix.";

return 0;

int A[m][n], B[p][q], C[m][q];

cout << "Enter elements of matrix A:" << endl;

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

cin >> A[i][j];

cout << "Enter elements of matrix B:" << endl;

for (int i = 0; i < p; i++) {

for (int j = 0; j < q; j++) {

cin >> B[i][j];

for (int i = 0; i < m; i++) {

for (int j = 0; j < q; j++) {

 C[i][j] = 0;

for (int i = 0; i < m; i++) {

for (int j = 0; j < q; j++) {

for (int k = 0; k < n; k++) {

C[i][j] += A[i][k] * B[k][j];

cout << "The resulting matrix after multiplication is:" << endl;

for (int i = 0; i < m; i++) {

for (int j = 0; j < q; j++) {

cout << C[i][j] << " ";

cout << endl;

return 0;

Output
Q 4 . Linked list (insertion –beg,middle,end)

#include <iostream>

using namespace std

struct Node {

int data;

Node* next;

Node(int val) {

data = val;

next = nullptr;

};

class LinkedList {

private:
 Node* head;

public

LinkedList() {

head = nullptr;

void insertAtBeginning(int val) {

Node* newNode = new Node(val);

newNode->next = head;

head = newNode;

cout << "Inserted " << val << " at the beginning.\n";

void insertAtEnd(int val) {

Node* newNode = new Node(val);

if (head == nullptr) {

head = newNode;

} else {

Node* temp = head;

while (temp->next != nullptr) {

temp = temp->next;

temp->next = newNode;

cout << "Inserted " << val << " at the end.\n";

void insertAtMiddle(int val, int position) {

if (position <= 0) {
 cout << "Position must be greater than 0.\n";

return;

Node* newNode = new Node(val);

if (position == 1) {

newNode->next = head;

head = newNode;

cout << "Inserted " << val << " at position " << position << ".\n";

return;

Node* temp = head;

int count = 1;

while (temp != nullptr && count < position - 1) {

temp = temp->next;

count++;

if (temp == nullptr) {

cout << "The position is greater than the list size.\n";

return;

newNode->next = temp->next;

temp->next = newNode;

cout << "Inserted " << val << " at position " << position << ".\n";

void printList() {

if (head == nullptr) {
 cout << "List is empty.\n";

return;

Node* temp = head;

while (temp != nullptr) {

cout << temp->data << " -> ";

temp = temp->next;

cout << "NULL\n";

};

int main() {

LinkedList list;

list.insertAtBeginning(10);

list.insertAtEnd(20);

list.insertAtEnd(30);

list.insertAtMiddle(15, 2); // Insert 15 at position 2

list.insertAtMiddle(25, 4); // Insert 25 at position

cout << "Linked List: ";

list.printList();

return 0;

Output
Q 5. Linked list (Deletion –Beg,Middle,End)

#include <iostream>

using namespace std;

struct Node {

int data;

Node* next;

Node(int val) {

data = val;

next = nullptr;

};

void insertEnd(Node*& head, int value) {

Node* newNode = new Node(value);

if (!head) {

head = newNode;

return;

Node* temp = head;

while (temp->next) {
 temp = temp->next;

temp->next = newNode;

void deleteBegin(Node*& head) {

if (head == nullptr) {

cout << "List is empty!" << endl;

return;

Node* temp = head;

head = head->next;

delete temp;

void deleteEnd(Node*& head) {

if (head == nullptr) {

cout << "List is empty!" << endl;

return;

if (head->next == nullptr) { // Only one node in the list

delete head;

head = nullptr;

return;

Node* temp = head;

while (temp->next && temp->next->next) { // Traverse to second last node

temp = temp->next;
 }

delete temp->next; // Delete the last node

temp->next = nullptr; // Set second last node's next pointer to null

void deleteMiddle(Node*& head, int value) {

if (head == nullptr) {

cout << "List is empty!" << endl;

return;

Node* temp = head;

while (temp != nullptr && temp->next != nullptr) {

if (temp->next->data == value) {

Node* toDelete = temp->next;

temp->next = temp->next->next;

delete toDelete;

cout << "Deleted " << value << " from the list." << endl;

return;

temp = temp->next;

cout << "Value not found in the list!" << endl;

void display(Node* head) {

if (head == nullptr) {

cout << "List is empty!" << endl;

return;
 }

Node* temp = head;

while (temp) {

cout << temp->data << " -> ";

temp = temp->next;

cout << "NULL" << endl;

int main() {

Node* head = nullptr;

insertEnd(head, 10);

insertEnd(head, 20);

insertEnd(head, 30);

insertEnd(head, 40);

insertEnd(head, 50);

cout << "Initial Linked List: ";

display(head);

deleteBegin(head);

cout << "After deleting the beginning node: ";

display(head);

deleteEnd(head);

cout << "After deleting the end node: ";

display(head

deleteMiddle(head, 30);

cout << "After deleting the middle node with value 30: ";
 display(head);

return 0;

Output

Q 6.Doubly linked list (implementation )

#include <stdio.h>

#include <stdlib.h>

struct Node {

int data;

struct Node* prev;

struct Node* next;

};

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;

void insertAtBeginning(struct Node** head, int data) {

struct Node* newNode = createNode(data);

newNode->next = *head;

if (*head != NULL) {

(*head)->prev = newNode;

*head = newNode;

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;

void deleteNode(struct Node** head, int data) {

struct Node* temp = *head;

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

 temp = temp->next;

if (temp == NULL) {

printf("Node with data %d not found.\n", data);

return;

if (*head == temp) {

*head = temp->next;

if (temp->next != NULL) {

temp->next->prev = temp->prev;

if (temp->prev != NULL) {

temp->prev->next = temp->next;

free(temp);

void printListForward(struct Node* head) {

struct Node* temp = head;

while (temp != NULL) {

printf("%d <-> ", temp->data);

temp = temp->next;

printf("NULL\n")

void printListBackward(struct Node* head) {

struct Node* temp = head;

 while (temp != NULL && temp->next != NULL) {

temp = temp->next;

while (temp != NULL) {

printf("%d <-> ", temp->data);

temp = temp->prev;

printf("NULL\n");

int main() {

struct Node* head = NULL;

insertAtBeginning(&head, 10);

insertAtBeginning(&head, 20);

insertAtBeginning(&head, 30);

printf("List after inserting at the beginning: ");

printListForward(head);

insertAtEnd(&head, 40);

insertAtEnd(&head, 50);

printf("List after inserting at the end: ");

printListForward(head);

deleteNode(&head, 20);

printf("List after deleting node with data 20: ");

printListForward(head);

printf("List printed backward: ");

printListBackward(head);

return 0;
}

Output

Q 7. Stack(Implementation –push,pop,array / linked list )

Stack implementation using linked list ..

#include <iostream>

using namespace std;

class Node {

public:

int data;

Node* next;

};

class StackLinkedList {

private:

Node* top;

public:

StackLinkedList() {
 top = nullptr;

~StackLinkedList() {

while (!isEmpty()) {

pop();

bool isEmpty() {

return top == nullptr;

void push(int value) {

Node* newNode = new Node();

newNode->data = value;

newNode->next = top;

top = newNode;

cout << value << " pushed into stack" << endl;

int pop() {

if (isEmpty()) {

cout << "Stack underflow! No element to pop" << endl;

return -1; // returning -1 to indicate underflow

int poppedValue = top->data;

Node* temp = top;

top = top->next;

delete temp;
 return poppedValue;

int peek() {

if (isEmpty()) {

cout << "Stack is empty!" << endl;

return -1;

return top->data;

};

int main() {

StackLinkedList stack;

stack.push(10);

stack.push(20);

stack.push(30);

stack.push(40);

stack.push(50);

cout << "Top element is: " << stack.peek() << endl;

cout << stack.pop() << " popped from stack" << endl;

cout << stack.pop() << " popped from stack" << endl;

return 0;

OUTPUT
Q 8.Stack(Infix to postfix )

#include <iostream>

#include <stack>

#include <string>

using namespace std;

int precedence(char op) {

if (op == '+' || op == '-') return 1;

if (op == '*' || op == '/') return 2;

if (op == '^') return 3; // For exponentiation

return 0;

bool isOperator(char c) {

return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';

string infixToPostfix(string infix) {

stack<char> s;

string postfix = "

for (char c : infix) {

if (isalnum(c)) {

postfix += c;

else if (c == '(') {

s.push(c);

else if (c == ')') {

while (!s.empty() && s.top() != '(') {

postfix += s.top();

s.pop();

s.pop(); // Remove '('

else if (isOperator(c)) {

while (!s.empty() && precedence(s.top()) >= precedence(c)) {

postfix += s.top();

s.pop();

s.push(c);

while (!s.empty()) {

postfix += s.top();

s.pop();

}
 return postfix;

int main() {

string infix;

cout << "Enter an infix expression: ";

cin >> infix;

string postfix = infixToPostfix(infix);

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

return 0;

Output

Q 9 . Stack (Postfix Evaluation )

#include <iostream>

#include <stack>

#include <string>

#include <cctype> // for isdigit()

using namespace std;

int evaluatePostfix(const string& expression) {

stack<int> stack;

for (char ch : expression) {

// If the character is an operand, push it to the stack

if (isdigit(ch)) {

stack.push(ch - '0'); // Convert character to integer

else {

if (stack.size() < 2) {

cout << "Invalid postfix expression!" << endl;

return -1;

int operand2 = stack.top(); // Second operand

stack.pop();

int operand1 = stack.top(); // First operand

stack.pop();

switch (ch) {

case '+':

stack.push(operand1 + operand2);

break;

case '-':

stack.push(operand1 - operand2);

break;

case '*':

stack.push(operand1 * operand2);

break;

case '/':

if (operand2 == 0) {

cout << "Division by zero error!" << endl;

 return -1;

stack.push(operand1 / operand2);

break;

default:

cout << "Unknown operator: " << ch << endl;

return -1;

if (stack.size() == 1) {

return stack.top();

} else {

cout << "Invalid postfix expression!" << endl;

return -1;

int main() {

string postfixExpression;

cout << "Enter a postfix expression: ";

cin >> postfixExpression;

int result = evaluatePostfix(postfixExpression);

if (result != -1) {

cout << "Result: " << result << endl;

return 0;
}

Output

Q 10. Queue

#include <stdio.h>

#include <stdlib.h>

#define MAX 5 // Maximum size of the queue

struct Queue {

int items[MAX];

int front;

int rear;

};

void initializeQueue(struct Queue* q) {

q->front = -1;

q->rear = -1;

int isEmpty(struct Queue* q) {

return (q->front == -1);

int isFull(struct Queue* q) {

return (q->rear == MAX - 1);

}
void enqueue(struct Queue* q, int value) {

if (isFull(q)) {

printf("Queue is full! Cannot enqueue %d\n", value);

return;

if (q->front == -1) {

q->front = 0; // If queue is empty, set front to 0

q->rear++;

q->items[q->rear] = value;

printf("Enqueued %d\n", value);

// Function to remove an element from the queue (dequeue)

int dequeue(struct Queue* q) {

if (isEmpty(q)) {

printf("Queue is empty! Cannot dequeue.\n");

return -1;

int value = q->items[q->front]

if (q->front == q->rear) {

q->front = q->rear = -1;

} else {

q->front++;

return value;

}
void display(struct Queue* q) {

if (isEmpty(q)) {

printf("Queue is empty.\n");

return;

printf("Queue: ");

for (int i = q->front; i <= q->rear; i++) {

printf("%d ", q->items[i]);

printf("\n");

// Main function

int main() {

struct Queue q;

initializeQueue(&q);

enqueue(&q, 10);

enqueue(&q, 20);

enqueue(&q, 30);

enqueue(&q, 40);

enqueue(&q, 50);

display(&q);

int dequeuedValue = dequeue(&q);

if (dequeuedValue != -1) {

printf("Dequeued %d\n", dequeuedValue);

display(&q);
 enqueue(&q, 60);

display(&q);

return 0;

OUTPUT

Q 11 . Circular Queue

#include <iostream>

using namespace std;

class CircularQueue {

private:

int *queue;

int front, rear, size, capacity;

public:

CircularQueue(int cap) {

capacity = cap;

queue = new int[capacity];

 front = -1;

rear = -1;

size = 0;

~CircularQueue() {

delete[] queue;

bool isEmpty() {

return size == 0;

bool isFull() {

return size == capacity;

// Add an element to the queue

void enqueue(int value) {

if (isFull()) {

cout << "Queue is full! Cannot enqueue " << value << endl;

return;

if (isEmpty()) {

front = rear = 0;

} else {

rear = (rear + 1) % capacity;

queue[rear] = value;

size++;
 cout << "Enqueued: " << value << endl;

int dequeue() {

if (isEmpty()) {

cout << "Queue is empty! Cannot dequeue." << endl;

return -1;

int value = queue[front];

if (front == rear) { // Only one element left

front = rear = -1;

} else {

front = (front + 1) % capacity;

size--;

cout << "Dequeued: " << value << endl;

return value;

// Get the front element of the queue

int peek() {

if (isEmpty()) {

cout << "Queue is empty!" << endl;

return -1;

return queue[front];

}
 // Display the elements in the queue

void display() {

if (isEmpty()) {

cout << "Queue is empty!" << endl;

return;

cout << "Queue elements: ";

int i = front;

do {

cout << queue[i] << " ";

i = (i + 1) % capacity;

} while (i != (rear + 1) % capacity);

cout << endl;

};

int main() {

int capacity;

cout << "Enter the capacity of the circular queue: ";

cin >> capacity;

CircularQueue cq(capacity);

cq.enqueue(10);

cq.enqueue(20);

cq.enqueue(30);

cq.display();

cq.dequeue();

cq.display();
 cq.enqueue(40);

cq.enqueue(50);

cq.display();

cq.dequeue();

cq.enqueue(60);

cq.display();

return 0;

Output

Q 12 . Searching –Linear Binary

#include <iostream>

#include <algorithm> // For std::sort

using namespace std;

// Linear Search Function

int linearSearch(int arr[], int n, int key) {

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

if (arr[i] == key) {

return i; // Return the index where the key is found

return -1; // Key not found

// Binary Search Function

int binarySearch(int arr[], int n, int key) {

int low = 0, high = n - 1;

while (low <= high) {

int mid = low + (high - low) / 2; // Avoids overflow

if (arr[mid] == key) {

return mid; // Return the index where the key is found

} else if (arr[mid] < key) {

low = mid + 1;

} else {

high = mid - 1;

return -1; // Key not found

int main() {

int n, key;
cout << "Enter the number of elements in the array: ";

cin >> n;

int arr[n];

cout << "Enter the elements of the array: ";

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

cin >> arr[i];

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

cin >> key;

// Linear Search

int linResult = linearSearch(arr, n, key);

if (linResult != -1) {

cout << "Linear Search: Key found at index " << linResult << endl;

} else {

cout << "Linear Search: Key not found" << endl;

// Binary Search

sort(arr, arr + n);

int binResult = binarySearch(arr, n, key);

if (binResult != -1) {

cout << "Binary Search: Key found at index " << binResult << " (after sorting)" << endl;

} else {

cout << "Binary Search: Key not found" << endl;

return 0;
}

OUTPUT

Q 13. Sorting- Bubble,Selection ,Insertion ,Merge

#include <iostream>

#include <vector>

using namespace std

void printArray(vector<int>& arr) {

for (int i : arr) {

cout << i << " ";

cout << endl;

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

// Selection Sort

void selectionSort(vector<int>& arr) {

int n = arr.size();

for (int i = 0; i < n - 1; i++) {

int minIndex = i;

for (int j = i + 1; j < n; j++) {

if (arr[j] < arr[minIndex]) {

minIndex = j;

swap(arr[i], arr[minIndex]);

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

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 j = 0; j < n2; j++)

R[j] = arr[mid + 1 + j];

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

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

}
 k++;

while (i < n1) {

arr[k] = L[i];

i++;

k++;

while (j < n2) {

arr[k] = R[j];

j++;

k++;

// Merge Sort

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

int main() {

vector<int> arr = {64, 34, 25, 12, 22, 11, 90};

cout << "Original array: ";

printArray(arr);
 // Bubble Sort

vector<int> bubbleArr = arr;

bubbleSort(bubbleArr);

cout << "Bubble Sorted array: ";

printArray(bubbleArr)

// Selection Sort

vector<int> selectionArr = arr;

selectionSort(selectionArr);

cout << "Selection Sorted array: ";

printArray(selectionArr);

vector<int> insertionArr = arr;

insertionSort(insertionArr);

cout << "Insertion Sorted array: ";

printArray(insertionArr);

vector<int> mergeArr = arr;

mergeSort(mergeArr, 0, mergeArr.size() - 1);

cout << "Merge Sorted array: ";

printArray(mergeArr);

return 0;

OUTPUT
Q 14. Binary Tree(Implementation )

#include <iostream>

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; // Pointer to the root node

BinaryTree() {
 root = nullptr;

void insert(int value) {

root = insertHelper(root, value);

void inorderTraversal() {

inorderHelper(root);

cout << endl;

void preorderTraversal() {

preorderHelper(root);

cout << endl;

void postorderTraversal() {

postorderHelper(root);

cout << endl;

private:

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

if (node == nullptr) {

return new Node(value); // Create a new node if the current one is null

if (value < node->data) {

node->left = insertHelper(node->left, value); // Insert in the left subtree

} else {

node->right = insertHelper(node->right, value); // Insert in the right subtree

 }

return node;

void inorderHelper(Node* node) {

if (node != nullptr) {

inorderHelper(node->left); // Visit left child

cout << node->data << " "; // Visit current node

inorderHelper(node->right); // Visit right child

void preorderHelper(Node* node) {

if (node != nullptr) {

cout << node->data << " "; // Visit current node

preorderHelper(node->left); // Visit left child

preorderHelper(node->right); // Visit right child

void postorderHelper(Node* node) {

if (node != nullptr) {

postorderHelper(node->left); // Visit left child

postorderHelper(node->right); // Visit right child

cout << node->data << " "; // Visit current node

};

int main() {
 BinaryTree tree;

tree.insert(10);

tree.insert(5);

tree.insert(15);

tree.insert(3);

tree.insert(7);

cout << "In-order Traversal: ";

tree.inorderTraversal();

cout << "Pre-order Traversal: ";

tree.preorderTraversal();

cout << "Post-order Traversal: ";

tree.postorderTraversal();

return 0;

OUTPUT

Q 15. Binary Search Tree( Insertion ,Deletion)

#include <iostream>

using namespace std;

struct Node {
 int data;

Node* left;

Node* right;

Node(int val) {

data = val;

left = nullptr;

right = nullptr;

};

class BST {

public:

Node* root;

BST() { root = nullptr; }

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

if (node == nullptr) {

return new Node(val);

if (val < node->data) {

node->left = insert(node->left, val);

} else if (val > node->data) {

node->right = insert(node->right, val);

return node;

void insert(int val) {

root = insert(root, val);

}

Node* findMin(Node* node) {

while (node && node->left != nullptr) {

node = node->left;

return node;

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

if (node == nullptr) {

return node;

if (val < node->data) {

node->left = deleteNode(node->left, val);

} else if (val > node->data) {

node->right = deleteNode(node->right, val);

} else {

if (node->left == nullptr) {

Node* temp = node->right;

delete node;

return temp;

} else if (node->right == nullptr) {

Node* temp = node->left;

delete node;

return temp;

Node* temp = findMin(node->right);

 node->data = temp->data;

node->right = deleteNode(node->right, temp->data);

return node;

void deleteNode(int val) {

root = deleteNode(root, val);

void inOrder(Node* node) {

if (node != nullptr) {

inOrder(node->left);

cout << node->data << " ";

inOrder(node->right);

void inOrder() {

inOrder(root);

cout << endl;

};

int main() {

BST tree;

tree.insert(50);

tree.insert(30);

tree.insert(70);

tree.insert(20);
 tree.insert(40);

tree.insert(60);

tree.insert(80);

cout << "In-order traversal of the BST: ";

tree.inOrder();

cout << "Deleting 20\n";

tree.deleteNode(20);

cout << "In-order traversal after deletion: ";

tree.inOrder();

cout << "Deleting 30\n";

tree.deleteNode(30);

cout << "In-order traversal after deletion: ";

tree.inOrder();

cout << "Deleting 50\n";

tree.deleteNode(50);

cout << "In-order traversal after deletion: ";

tree.inOrder()

return 0;

OUTPUT
Q 16. Binary Search Tree (Inorder,Preorder,Postorder,Traversal)

#include <iostream>

using namespace std;

struct Node {

int data;

Node* left;

Node* right;

Node(int value) {

data = value;

left = nullptr;

right = nullptr;

};

class BST {
private:

Node* root

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

if (node == nullptr) {

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;

void inorderTraversal(Node* node) {

if (node == nullptr) return;

inorderTraversal(node->left);

cout << node->data << " ";

inorderTraversal(node->right);

void preorderTraversal(Node* node) {

if (node == nullptr) return;

cout << node->data << " ";

preorderTraversal(node->left);

preorderTraversal(node->right);
 }

void postorderTraversal(Node* node) {

if (node == nullptr) return;

postorderTraversal(node->left);

postorderTraversal(node->right);

cout << node->data << " ";

public:

BST() {

root = nullptr;

void insert(int value) {

root = insert(root, value);

void inorder() {

cout << "Inorder Traversal: ";

inorderTraversal(root);

cout << endl;

void preorder() {

cout << "Preorder Traversal: ";

preorderTraversal(root);

cout << endl;

void postorder() {
 cout << "Postorder Traversal: ";

postorderTraversal(root);

cout << endl;

};

int main() {

BST bst;

bst.insert(50);

bst.insert(30);

bst.insert(70);

bst.insert(20);

bst.insert(40);

bst.insert(60);

bst.insert(80);

bst.inorder(); // Inorder Traversal

bst.preorder(); // Preorder Traversal

bst.postorder(); // Postorder Traversal

return 0;

OUTPUT
Q 17. A V L Tree (Insertion,Deletion)

#include <iostream>

using namespace std;

struct Node {

int key;

Node* left;

Node* right;

int height;

int height(Node* node) {

return node == nullptr ? 0 : node->height;

Node* createNode(int key) {

Node* node = new Node();

node->key = key;

node->left = nullptr;

node->right = nullptr;

node->height = 1;

return node;

}
int getBalance(Node* node) {

return node == nullptr ? 0 : height(node->left) - height(node->right);

Node* rightRotate(Node* y) {

Node* x = y->left;

Node* T2 = x->right;

x->right = y;

y->left = T2;

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

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

return x;

Node* leftRotate(Node* x) {

Node* y = x->right;

Node* T2 = y->left;

y->left = x;

x->right = T

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

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

return y;

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

// Perform normal BST insertion

if (node == nullptr)

return createNode(key);

if (key < node->key)

 node->left = insert(node->left, key);

else if (key > node->key)

node->right = insert(node->right, key);

else // Duplicate keys are not allowed

return node;

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

int balance = getBalance(node)

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;

while (current->left != nullptr)

current = current->left;

return current;
}

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

if (root == nullptr)

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 == nullptr) || (root->right == nullptr)) {

Node* temp = root->left ? root->left : root->right;

if (temp == nullptr) {

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 == nullptr)

return root;

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

 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 != nullptr) {

inOrder(root->left);

cout << root->key << " ";

inOrder(root->right);

int main() {

Node* root = nullptr;

root = insert(root, 10);

root = insert(root, 20);

 root = insert(root, 30);

root = insert(root, 40);

root = insert(root, 50);

root = insert(root, 25);

cout << "Inorder traversal of the constructed AVL tree is: ";

inOrder(root);

cout << endl;

root = deleteNode(root, 30);

cout << "Inorder traversal after deletion of 30: ";

inOrder(root);

cout << endl;

return 0;

OUTPUT

Q 18. B – Tree

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std

const int T = 3;

class BTreeNode {

public:

vector<int> keys;

vector<BTreeNode*> children;

bool isLeaf;

BTreeNode(bool leaf = true) : isLeaf(leaf) {

void insertNonFull(int key);

void splitChild(int i, BTreeNode* y);

};

class BTree {

public:

BTreeNode* root;

BTree() {

root = new BTreeNode(true);

void insert(int key);

void traverse(BTreeNode* node);

};

void BTreeNode::insertNonFull(int key) {

int i = keys.size() - 1;

if (isLeaf) {

while (i >= 0 && keys[i] > key) {

i--;

keys.insert(keys.begin() + i + 1, key);
 } else {

while (i >= 0 && keys[i] > key) {

i--;

i++;

if (children[i]->keys.size() == 2 * T - 1) {

splitChild(i, children[i]);

if (keys[i] < key) {

i++;

children[i]->insertNonFull(key);

}
void BTreeNode::splitChild(int i, BTreeNode* y) {

BTreeNode* z = new BTreeNode(y->isLeaf);

z->keys.resize(T - 1);

for (int j = 0; j < T - 1; j++) {

z->keys[j] = y->keys[j + T];

if (!y->isLeaf) {

z->children.resize(T);

for (int j = 0; j < T; j++) {

z->children[j] = y->children[j + T];

}
 y->keys.resize(T - 1);

children.insert(children.begin() + i + 1, z);

keys.insert(keys.begin() + i, y->keys[T - 1]);

void BTree::insert(int key) {

if (root->keys.size() == 2 * T - 1) {

BTreeNode* newNode = new BTreeNode(false);

newNode->children.push_back(root);

newNode->splitChild(0, root);

int i = 0;

if (newNode->keys[0] < key) {

i++;

newNode->children[i]->insertNonFull(key);

root = newNode;

} else {

root->insertNonFull(key);

void BTree::traverse(BTreeNode* node) {

if (node == nullptr) {

return;

for (int i = 0; i < node->keys.size(); i++) {

if (!node->isLeaf) {

traverse(node->children[i]);
 }

cout << node->keys[i] << " ";

if (!node->isLeaf) {

traverse(node->children[node->keys.size()]);

int main() {

BTree tree;

tree.insert(10);

tree.insert(20);

tree.insert(5);

tree.insert(6);

tree.insert(12);

tree.insert(30);

tree.insert(7);

tree.insert(17);

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

tree.traverse(tree.root);

cout << endl;

return 0;

OUTPUT
Q 19.B+ Tree

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

class BPlusNode {

public:

bool isLeaf;

vector<int> keys;

vector<BPlusNode*> children;

vector<int> values;

BPlusNode(bool leaf = false) {

isLeaf = leaf;

};

class BPlusTree {

private:

int order; // The maximum number of children per node

BPlusNode* root; // The root of the tree

void splitNode(BPlusNode* node, BPlusNode* parent, int index) {

int mid = node->keys.size() / 2;

BPlusNode* newNode = new BPlusNode(node->isLeaf);

newNode->keys.assign(node->keys.begin() + mid, node->keys.end());

node->keys.resize(mid);

if (node->isLeaf) {

newNode->values.assign(node->values.begin() + mid, node->values.end());

node->values.resize(mid);

} else {

newNode->children.assign(node->children.begin() + mid + 1, node->children.end());

node->children.resize(mid + 1);

if (parent == nullptr) {

root = new BPlusNode(false);

parent = root;

parent->keys.push_back(newNode->keys[0]);

parent->children.push_back(node);

parent->children.push_back(newNode);

} else {

parent->keys.insert(parent->keys.begin() + index, newNode->keys[0]);

parent->children.insert(parent->children.begin() + index + 1, newNode);

void insertInLeafNode(BPlusNode* leaf, int key, int value) {

auto it = lower_bound(leaf->keys.begin(), leaf->keys.end(), key);

leaf->keys.insert(it, key);
 leaf->values.insert(leaf->values.begin() + distance(leaf->keys.begin(), it), value);

void insertRecursive(BPlusNode* node, int key, int value) {

if (node->isLeaf) {

insertInLeafNode(node, key, value);

if (node->keys.size() > order - 1) {

splitNode(node, nullptr, 0);

} else {

int index = lower_bound(node->keys.begin(), node->keys.end(), key) - node-

>keys.begin();

insertRecursive(node->children[index], key, value);

if (node->children[index]->keys.size() > order - 1) {

splitNode(node->children[index], node, index);

int searchRecursive(BPlusNode* node, int key) {

if (node->isLeaf) {

auto it = lower_bound(node->keys.begin(), node->keys.end(), key);

if (it != node->keys.end() && *it == key) {

return node->values[it - node->keys.begin()];

} else {

return -1;

} else {
 int index = lower_bound(node->keys.begin(), node->keys.end(), key) - node-
>keys.begin();

return searchRecursive(node->children[index], key);

public:

BPlusTree(int order) {

this->order = order;

root = new BPlusNode(true); // Initialize the root as a leaf node

void insert(int key, int value) {

if (root->keys.size() == order - 1) {

BPlusNode* newRoot = new BPlusNode(false);

newRoot->children.push_back(root);

splitNode(root, newRoot, 0);

root = newRoot;

insertRecursive(root, key, value);

int search(int key) {

return searchRecursive(root, key);

void printTree(BPlusNode* node, int level = 0) {

cout << string(level, ' ') << "Level " << level << ": ";

for (int key : node->keys) {

cout << key << " ";

 }

cout << endl;

if (!node->isLeaf) {

for (BPlusNode* child : node->children) {

printTree(child, level + 1);

void print() {

printTree(root);

};

int main() {

BPlusTree tree(3); // Create a B+ tree of order 3 (max 2 keys per node)

tree.insert(10, 100);

tree.insert(20, 200);

tree.insert(5, 50);

tree.insert(6, 60);

tree.insert(30, 300);

tree.insert(40, 400);

cout << "Tree Structure:" << endl;

tree.print();

cout << "\nSearching for key 10: " << tree.search(10) << endl; // Should return 100

cout << "Searching for key 20: " << tree.search(20) << endl; // Should return 200

cout << "Searching for key 50: " << tree.search(50) << endl; // Should return -1 (not found)

return 0;
}

OUTPUT

Q 20. Graphs (Djikstra Algo)

#include <iostream>

#include <climits>

#include <vector>

using namespace std;

int minDistance(const vector<int>& dist, const vector<bool>& sptSet, int V) {

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++) {

if (!sptSet[v] && dist[v] <= min) {

min = dist[v];

min_index = v;

return min_index;

void dijkstra(const vector<vector<int>>& graph, int src, int V) {

 vector<int> dist(V, INT_MAX); // I

vector<bool> sptSet(V, false); // Shortest Path Tree set

dist[src] = 0;

for (int count = 0; count < V - 1; count++) {

int u = minDistance(dist, sptSet, V);

sptSet[u] = true;

for (int v = 0; v < V; v++) {

// Update dist[v] if and only if v is not in sptSet, there is an edge from u to v,

// and the total weight of path from source to v through u is less than the current
distance of v

if (!sptSet[v] && graph[u][v] != 0 && dist[u] != INT_MAX && dist[u] + graph[u][v] <
dist[v]) {

dist[v] = dist[u] + graph[u][v];

cout << "Vertex\tDistance from Source " << src << endl;

for (int i = 0; i < V; i++) {

if (dist[i] == INT_MAX)

cout << i << "\tINF" << endl;

else

cout << i << "\t" << dist[i] << endl;

int main() {

int V = 9; // Number of vertices in the graph

 vector<vector<int>> graph = {

{0, 4, 0, 0, 0, 0, 0, 8, 0},

{4, 0, 8, 0, 0, 0, 0, 11, 0},

{0, 8, 0, 7, 0, 4, 0, 0, 2},

{0, 0, 7, 0, 9, 14, 0, 0, 0},

{0, 0, 0, 9, 0, 10, 0, 0, 0},

{0, 0, 4, 14, 10, 0, 2, 0, 0},

{0, 0, 0, 0, 0, 2, 0, 1, 6},

{8, 11, 0, 0, 0, 0, 1, 0, 7},

{0, 0, 2, 0, 0, 0, 6, 7, 0}

};

return 0;

OUTPUT