Data Structures using C++

Course Code 21EC584

Course Objectives

• To write and execute programs in C++ to solve problems using data structures such as arrays,
linked lists, stacks, queues, trees, graphs and search trees.

• To learn to write C++programs to implement various sorting and searching algorithms

Experiments

1. Write a C++ program that uses functions to perform the following:

a) Create a singly linked list of integers. b) Delete a given integer from the above linked list.
c) Display the contents of the above list after deletion.

#include <iostream>

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

struct Node {

int data;

Node* next;

};

// Function to create a new node with given data

Node* createNode(int data) {

Node* newNode = new Node;

newNode->data = data;

newNode->next = nullptr;

return newNode;

// Function to insert a new node at the end of the linked list

void insertAtEnd(Node*& head, int data) {

 Node* newNode = createNode(data);

if (head == nullptr) {

// If the list is empty, the new node becomes the head

head = newNode;

} else {

// Traverse the list to find the last node

Node* current = head;

while (current->next != nullptr) {

current = current->next;

// Append the new node to the end of the list

current->next = newNode;

// Function to delete a given integer from the linked list

void deleteNode(Node*& head, int target) {

// If the list is empty, do nothing

if (head == nullptr) {

return;

// If the target is at the head of the list

if (head->data == target) {

Node* temp = head;

 head = head->next;

delete temp;

return;

// Traverse the list to find the node before the target

Node* current = head;

while (current->next != nullptr && current->next->data != target) {

current = current->next;

// If the target is found, delete the node

if (current->next != nullptr) {

Node* temp = current->next;

current->next = current->next->next;

delete temp;

// Function to display the elements of the linked list

void displayList(const Node* head) {

const Node* current = head;

while (current != nullptr) {

std::cout << current->data << " ";

current = current->next;

std::cout << std::endl;

}

// Main function

int main() {

// Initialize an empty linked list

Node* head = nullptr;

// Insert nodes into the linked list

insertAtEnd(head, 1);

insertAtEnd(head, 2);

insertAtEnd(head, 3);

insertAtEnd(head, 4);

insertAtEnd(head, 5);

// Display the original linked list

std::cout << "Original Linked List: ";

displayList(head);

// Delete a given integer from the linked list

int targetToDelete = 3;

deleteNode(head, targetToDelete);

// Display the modified linked list

std::cout << "Linked List after Deletion of " << targetToDelete << ": ";

displayList(head);

// Free the allocated memory for the linked list

 Node* current = head;

while (current != nullptr) {

Node* nextNode = current->next;

delete current;

current = nextNode;

return 0;

2. Write a C++ programs to implement i) Bubble sort ii) Selection sort iii) quick sort iv) insertion
sort

#include <iostream>

void bubbleSort(int arr[], int n) {

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] and arr[j + 1] if they are in the wrong order
std::swap(arr[j], arr[j + 1]);
}
}
}
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

bubbleSort(arr, n);

std::cout << "Sorted array: ";

for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}

return 0;
}

#include <iostream>

void selectionSort(int arr[], int n) {

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 the found minimum element with the first element
std::swap(arr[i], arr[minIndex]);
}
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

selectionSort(arr, n);

std::cout << "Sorted array: ";

for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}

return 0;
}
#include <iostream>

int partition(int arr[], int low, int high) {

int pivot = arr[high];
int i = (low - 1);

for (int j = low; j <= high - 1; ++j) {

if (arr[j] < pivot) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pivotIndex = partition(arr, low, high);

quickSort(arr, low, pivotIndex - 1);

quickSort(arr, pivotIndex + 1, high);
}
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, n - 1);

std::cout << "Sorted array: ";

for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}

return 0;
}
#include <iostream>

void insertionSort(int arr[], int n) {

for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;

// Move elements of arr[0..i-1] that are greater than key to one position ahead of their
current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
 insertionSort(arr, n);

std::cout << "Sorted array: ";

for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}

return 0;
}

3. Write a C++ programs to implement the following using an array.

a) Stack ADT b) Queue AD

#include <iostream>

class Stack {

private:

static const int maxSize = 100;

int arr[maxSize];

int top;

public:

Stack() : top(-1) {}

void push(int data) {

if (top >= maxSize - 1) {

std::cout << "Stack Overflow: Cannot push element, stack is full." << std::endl;

} else {

arr[++top] = data;

std::cout << "Pushed " << data << " to the stack." << std::endl;

}
 void pop() {

if (top < 0) {

std::cout << "Stack Underflow: Cannot pop element, stack is empty." << std::endl;

} else {

std::cout << "Popped " << arr[top--] << " from the stack." << std::endl;

void display() {

if (top < 0) {

std::cout << "Stack is empty." << std::endl;

} else {

std::cout << "Stack elements: ";

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

std::cout << arr[i] << " ";

std::cout << std::endl;

};

int main() {

Stack stack;

stack.push(1);

stack.push(2);

stack.push(3);
 stack.display();

stack.pop();

stack.display();

stack.pop();

stack.display();

stack.pop();

stack.display();

return 0;

#include <iostream>

class Queue {

private:

static const int maxSize = 100;

int arr[maxSize];

int front, rear;

public:

Queue() : front(-1), rear(-1) {}

void enqueue(int data) {

if (rear == maxSize - 1) {
 std::cout << "Queue Overflow: Cannot enqueue element, queue is full." << std::endl;

} else {

if (front == -1) {

// If the queue is empty, set front to 0

front = 0;

arr[++rear] = data;

std::cout << "Enqueued " << data << " to the queue." << std::endl;

void dequeue() {

if (front == -1) {

std::cout << "Queue Underflow: Cannot dequeue element, queue is empty." << std::endl;

} else {

std::cout << "Dequeued " << arr[front++] << " from the queue." << std::endl;

if (front > rear) {

// Reset front and rear when the queue becomes empty

front = rear = -1;

void display() {

if (front == -1) {

std::cout << "Queue is empty." << std::endl;

} else {
 std::cout << "Queue elements: ";

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

std::cout << arr[i] << " ";

std::cout << std::endl;

};

int main() {

Queue queue;

queue.enqueue(1);

queue.enqueue(2);

queue.enqueue(3);

queue.display();

queue.dequeue();

queue.display();

queue.dequeue();

queue.display();

queue.dequeue();

queue.display();
 return 0;

4. Write a C++ programs to implement list ADT to perform following operations a) Insert an
element into a list. b) Delete an element from list c) Search for a key element in list d)count
number of nodes in list

#include <iostream>

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

struct Node {

int data;

Node* next;

};

class List {

private:

Node* head;

public:

List() : head(nullptr) {}

// Function to insert an element into the list

void insertElement(int data) {

Node* newNode = new Node{data, nullptr};

if (head == nullptr) {

// If the list is empty, the new node becomes the head

head = newNode;
 } else {

// Insert the new node at the beginning of the list

newNode->next = head;

head = newNode;

std::cout << "Inserted " << data << " into the list." << std::endl;

// Function to delete an element from the list

void deleteElement(int key) {

if (head == nullptr) {

std::cout << "List is empty. Cannot delete element." << std::endl;

return;

Node* current = head;

Node* prev = nullptr;

// Search for the key element in the list

while (current != nullptr && current->data != key) {

prev = current;

current = current->next;

if (current == nullptr) {

std::cout << "Element " << key << " not found in the list. Cannot delete." << std::endl;

} else {
 // Remove the node containing the key element

if (prev == nullptr) {

// If the key element is in the first node

head = current->next;

} else {

prev->next = current->next;

delete current;

std::cout << "Deleted element with value " << key << " from the list." << std::endl;

// Function to search for a key element in the list

void searchElement(int key) {

Node* current = head;

while (current != nullptr) {

if (current->data == key) {

std::cout << "Element " << key << " found in the list." << std::endl;

return;

current = current->next;

std::cout << "Element " << key << " not found in the list." << std::endl;

// Function to count the number of nodes in the list

 int countNodes() {

int count = 0;

Node* current = head;

while (current != nullptr) {

++count;

current = current->next;

return count;

};

int main() {

List myList;

myList.insertElement(1);

myList.insertElement(2);

myList.insertElement(3);

std::cout << "Number of nodes in the list: " << myList.countNodes() << std::endl;

myList.searchElement(2);

myList.deleteElement(2);

myList.searchElement(2);

std::cout << "Number of nodes in the list: " << myList.countNodes() << std::endl;
 return 0;

5. Write C++ programs to implement the following using a singly linked

list.Stack ADT b) Queue ADT

#include <iostream>

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

struct Node {

int data;

Node* next;

};

class Stack {

private:

Node* top;

public:

Stack() : top(nullptr) {}

// Function to push an element onto the stack

void push(int data) {

Node* newNode = new Node{data, nullptr};

newNode->next = top;

top = newNode;

std::cout << "Pushed " << data << " onto the stack." << std::endl;

}
 // Function to pop an element from the stack

void pop() {

if (top == nullptr) {

std::cout << "Stack Underflow: Cannot pop element, stack is empty." << std::endl;

} else {

Node* temp = top;

top = top->next;

std::cout << "Popped " << temp->data << " from the stack." << std::endl;

delete temp;

// Function to display the elements of the stack

void display() {

Node* current = top;

std::cout << "Stack elements: ";

while (current != nullptr) {

std::cout << current->data << " ";

current = current->next;

std::cout << std::endl;

};

int main() {

Stack stack;
 stack.push(1);

stack.push(2);

stack.push(3);

stack.display();

stack.pop();

stack.display();

stack.pop();

stack.display();

stack.pop();

stack.display();

return 0;

#include <iostream>

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

struct Node {

int data;

Node* next;

};

class Queue {
private:

Node* front;

Node* rear;

public:

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

// Function to enqueue an element into the queue

void enqueue(int data) {

Node* newNode = new Node{data, nullptr};

if (rear == nullptr) {

// If the queue is empty, set both front and rear to the new node

front = rear = newNode;

} else {

// Otherwise, add the new node to the end of the queue

rear->next = newNode;

rear = newNode;

std::cout << "Enqueued " << data << " into the queue." << std::endl;

// Function to dequeue an element from the queue

void dequeue() {

if (front == nullptr) {

std::cout << "Queue Underflow: Cannot dequeue element, queue is empty." << std::endl;

} else {

Node* temp = front;

 front = front->next;

if (front == nullptr) {

// If the queue becomes empty, update rear as well

rear = nullptr;

std::cout << "Dequeued " << temp->data << " from the queue." << std::endl;

delete temp;

// Function to display the elements of the queue

void display() {

Node* current = front;

std::cout << "Queue elements: ";

while (current != nullptr) {

std::cout << current->data << " ";

current = current->next;

std::cout << std::endl;

};

int main() {

Queue queue;

queue.enqueue(1);

queue.enqueue(2);
 queue.enqueue(3);

queue.display();

queue.dequeue();

queue.display();

queue.dequeue();

queue.display();

queue.dequeue();

queue.display();

return 0;

6. Write C++ programs to implement the deque (double ended queue)

ADT using a doubly linked list and an array.

#include <iostream>

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

struct Node {

int data;

Node* next;

Node* prev;

};

class Deque {
private:

Node* front;

Node* rear;

public:

Deque() : front(nullptr), rear(nullptr) {}

// Function to insert an element at the front of the deque

void insertFront(int data) {

Node* newNode = new Node{data, nullptr, nullptr};

if (front == nullptr) {

// If the deque is empty, set both front and rear to the new node

front = rear = newNode;

} else {

// Otherwise, add the new node to the front of the deque

newNode->next = front;

front->prev = newNode;

front = newNode;

std::cout << "Inserted " << data << " at the front of the deque." << std::endl;

// Function to insert an element at the rear of the deque

void insertRear(int data) {

Node* newNode = new Node{data, nullptr, nullptr};

if (rear == nullptr) {

// If the deque is empty, set both front and rear to the new node
 front = rear = newNode;

} else {

// Otherwise, add the new node to the rear of the deque

newNode->prev = rear;

rear->next = newNode;

rear = newNode;

std::cout << "Inserted " << data << " at the rear of the deque." << std::endl;

// Function to delete an element from the front of the deque

void deleteFront() {

if (front == nullptr) {

std::cout << "Deque Underflow: Cannot delete element, deque is empty." << std::endl;

} else {

Node* temp = front;

front = front->next;

if (front == nullptr) {

// If the deque becomes empty, update rear as well

rear = nullptr;

} else {

front->prev = nullptr;

std::cout << "Deleted element at the front of the deque." << std::endl;

delete temp;

}
// Function to delete an element from the rear of the deque

void deleteRear() {

if (rear == nullptr) {

std::cout << "Deque Underflow: Cannot delete element, deque is empty." << std::endl;

} else {

Node* temp = rear;

rear = rear->prev;

if (rear == nullptr) {

// If the deque becomes empty, update front as well

front = nullptr;

} else {

rear->next = nullptr;

std::cout << "Deleted element at the rear of the deque." << std::endl;

delete temp;

// Function to display the elements of the deque

void display() {

Node* current = front;

std::cout << "Deque elements: ";

while (current != nullptr) {

std::cout << current->data << " ";

current = current->next;

}
 std::cout << std::endl;

};

int main() {

Deque deque;

deque.insertFront(1);

deque.insertRear(2);

deque.insertFront(3);

deque.display();

deque.deleteFront();

deque.display();

deque.deleteRear();

deque.display();

deque.deleteFront();

deque.display();

return 0;

#include <iostream>

class Deque {
private:

static const int maxSize = 100;

int arr[maxSize];

int front;

int rear;

public:

Deque() : front(-1), rear(-1) {}

// Function to insert an element at the front of the deque

void insertFront(int data) {

if (front == -1) {

front = rear = 0;

arr[front] = data;

} else if ((front + 1) % maxSize == rear) {

std::cout << "Deque Overflow: Cannot insert element at the front, deque is full." <<
std::endl;

} else {

front = (front - 1 + maxSize) % maxSize;

arr[front] = data;

std::cout << "Inserted " << data << " at the front of the deque." << std::endl;

// Function to insert an element at the rear of the deque

void insertRear(int data) {

if (front == -1) {

front = rear = 0;
 arr[rear] = data;

} else if ((rear + 1) % maxSize == front) {

std::cout << "Deque Overflow: Cannot insert element at the rear, deque is full." <<
std::endl;

} else {

rear = (rear + 1) % maxSize;

arr[rear] = data;

std::cout << "Inserted " << data << " at the rear of the deque." << std::endl;

// Function to delete an element from the front of the deque

void deleteFront() {

if (front == -1) {

std::cout << "Deque Underflow: Cannot delete element from the front, deque is empty."
<< std::endl;

} else {

if (front == rear) {

// If only one element is present, reset front and rear

front = rear = -1;

} else {

front = (front + 1) % maxSize;

std::cout << "Deleted element from the front of the deque." << std::endl;

// Function to delete an element from the rear of the deque

 void deleteRear() {

if (front == -1) {

std::cout << "Deque Underflow: Cannot delete element from the rear, deque is empty."
<< std::endl;

} else {

if (front == rear) {

// If only one element is present, reset front and rear

front = rear = -1;

} else {

rear = (rear - 1 + maxSize) % maxSize;

std::cout << "Deleted element from the rear of the deque." << std::endl;

// Function to display the elements of the deque

void display() {

if (front == -1) {

std::cout << "Deque is empty." << std::endl;

} else {

std::cout << "Deque elements: ";

int i = front;

while (i != rear) {

std::cout << arr[i] << " ";

i = (i + 1) % maxSize;

std::cout << arr[rear] << " ";

std::cout << std::endl;

 }

};

int main() {

Deque deque;

deque.insertFront(

7. Write a C++ program to perform the following operations: a) Insert an element into a binary
search tree. b) Delete an element from a binary search tree. c) Search for a key element in a
binary search tree.

#include <iostream>

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

struct Node {

int data;

Node* left;

Node* right;

};

// Function to create a new node with given data

Node* createNode(int data) {

Node* newNode = new Node;

newNode->data = data;

newNode->left = newNode->right = nullptr;

return newNode;

}
// Function to insert an element into a binary search tree

Node* insert(Node* root, int data) {

if (root == nullptr) {

// If the tree is empty, create a new node

return createNode(data);

// Recursively insert into the left or right subtree based on the value

if (data < root->data) {

root->left = insert(root->left, data);

} else if (data > root->data) {

root->right = insert(root->right, data);

return root;

// Function to find the node with the minimum value in a BST

Node* findMinNode(Node* node) {

while (node->left != nullptr) {

node = node->left;

return node;

// Function to delete a node with the given key from a BST

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

if (root == nullptr) {

return root;

// Recursively search for the node to be deleted

if (key < root->data) {

root->left = deleteNode(root->left, key);

} else if (key > root->data) {

root->right = deleteNode(root->right, key);

} else {

// Node with only one child or no child

if (root->left == nullptr) {

Node* temp = root->right;

delete root;

return temp;

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

Node* temp = root->left;

delete root;

return temp;

// Node with two children, get the inorder successor (smallest in the right subtree)

Node* temp = findMinNode(root->right);

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

root->data = temp->data;
 // Delete the inorder successor

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

return root;

// Function to search for a key element in a BST

bool search(Node* root, int key) {

if (root == nullptr) {

return false;

if (key == root->data) {

return true;

} else if (key < root->data) {

return search(root->left, key);

} else {

return search(root->right, key);

// Function to perform an inorder traversal of a BST

void inorderTraversal(Node* root) {

if (root != nullptr) {

inorderTraversal(root->left);

std::cout << root->data << " ";

inorderTraversal(root->right);
 }

int main() {

Node* root = nullptr;

// Insert elements into the BST

root = insert(root, 50);

insert(root, 30);

insert(root, 20);

insert(root, 40);

insert(root, 70);

insert(root, 60);

insert(root, 80);

// Display the original BST

std::cout << "Original BST: ";

inorderTraversal(root);

std::cout << std::endl;

// Search for a key element

int searchKey = 40;

if (search(root, searchKey)) {

std::cout << "Element " << searchKey << " found in the BST." << std::endl;

} else {

std::cout << "Element " << searchKey << " not found in the BST." << std::endl;

}
 // Delete an element from the BST

int deleteKey = 30;

root = deleteNode(root, deleteKey);

// Display the modified BST after deletion

std::cout << "BST after deleting " << deleteKey << ": ";

inorderTraversal(root);

std::cout << std::endl;

// Free the allocated memory for the BST (not shown in the original question)

// You can add a function to free the memory after you are done with the BST

return 0;

8. Write C++ programs for implementing the following sorting methods:Merge sort b) Heap
sort

#include <iostream>

#include <vector>

void merge(std::vector<int>& arr, int left, int middle, int right) {

int n1 = middle - left + 1;

int n2 = right - middle;

// Create temporary arrays

std::vector<int> leftArray(n1);

std::vector<int> rightArray(n2);
// Copy data to temporary arrays leftArray[] and rightArray[]

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

leftArray[i] = arr[left + i];

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

rightArray[j] = arr[middle + 1 + j];

// Merge the temporary arrays back into arr[left..right]

int i = 0; // Initial index of first subarray

int j = 0; // Initial index of second subarray

int k = left; // Initial index of merged subarray

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

if (leftArray[i] <= rightArray[j]) {

arr[k] = leftArray[i];

++i;

} else {

arr[k] = rightArray[j];

++j;

++k;

// Copy the remaining elements of leftArray[], if there are any

while (i < n1) {

arr[k] = leftArray[i];

++i;
 ++k;

// Copy the remaining elements of rightArray[], if there are any

while (j < n2) {

arr[k] = rightArray[j];

++j;

++k;

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

if (left < right) {

// Same as (left + right) / 2, but avoids overflow for large left and right

int middle = left + (right - left) / 2;

// Sort first and second halves

mergeSort(arr, left, middle);

mergeSort(arr, middle + 1, right);

// Merge the sorted halves

merge(arr, left, middle, right);

int main() {

std::vector<int> arr = {12, 11, 13, 5, 6, 7};

 std::cout << "Original array: ";

for (int num : arr) {

std::cout << num << " ";

std::cout << std::endl;

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

std::cout << "Sorted array: ";

for (int num : arr) {

std::cout << num << " ";

std::cout << std::endl;

return 0;

Heap sort

#include <iostream>

#include <vector>

void heapify(std::vector<int>& arr, int n, int i) {

int largest = i; // Initialize largest as root

int left = 2 * i + 1; // Left child

int right = 2 * i + 2; // Right child

// If left child is larger than root

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

largest = left;

// If right child is larger than largest so far

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

largest = right;

// If largest is not root

if (largest != i) {

std::swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);

void heapSort(std::vector<int>& arr) {

int n = arr.size();

// Build heap (rearrange array)

for (int i = n / 2 - 1; i >= 0; --i) {

heapify(arr, n, i);

// One by one extract an element from the heap

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

// Move current root to the end

std::swap(arr[0], arr[i]);

// Call max heapify on the reduced heap

heapify(arr, i, 0);

int main() {

std::vector<int> arr = {12, 11, 13, 5, 6, 7};

std::cout << "Original array: ";

for (int num : arr) {

std::cout << num << " ";

std::cout << std::endl;

heapSort(arr);

std::cout << "Sorted array: ";

for (int num : arr) {

std::cout << num << " ";

std::cout << std::endl;

return 0;
}

9. Write C++ programs that use recursive functions to traverse the given binary tree in a)
Preorder b) inorder and c) postorder

#include <iostream>

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

struct Node {

int data;

Node* left;

Node* right;

};

// Function to create a new node with given data

Node* createNode(int data) {

Node* newNode = new Node;

newNode->data = data;

newNode->left = newNode->right = nullptr;

return newNode;

// Function for preorder traversal of a binary tree

void preorderTraversal(Node* root) {

if (root != nullptr) {

std::cout << root->data << " "; // Process the current node

preorderTraversal(root->left); // Traverse the left subtree

preorderTraversal(root->right); // Traverse the right subtree

}
// Function for inorder traversal of a binary tree

void inorderTraversal(Node* root) {

if (root != nullptr) {

inorderTraversal(root->left); // Traverse the left subtree

std::cout << root->data << " "; // Process the current node

inorderTraversal(root->right); // Traverse the right subtree

// Function for postorder traversal of a binary tree

void postorderTraversal(Node* root) {

if (root != nullptr) {

postorderTraversal(root->left); // Traverse the left subtree

postorderTraversal(root->right); // Traverse the right subtree

std::cout << root->data << " "; // Process the current node

int main() {

// Construct a sample binary tree

Node* root = createNode(1);

root->left = createNode(2);

root->right = createNode(3);

root->left->left = createNode(4);

root->left->right = createNode(5);

root->right->left = createNode(6);
 root->right->right = createNode(7);

// Perform preorder traversal

std::cout << "Preorder Traversal: ";

preorderTraversal(root);

std::cout << std::endl;

// Perform inorder traversal

std::cout << "Inorder Traversal: ";

inorderTraversal(root);

std::cout << std::endl;

// Perform postorder traversal

std::cout << "Postorder Traversal: ";

postorderTraversal(root);

std::cout << std::endl;

return 0;

10. Write a C++ program to perform the following operations a) Insertion into a B-tree b)
Deletion from a B-tree

#include <iostream>

#include <vector>

const int t = 2; // Minimum degree of the B-tree

// Define a structure for a B-tree node

struct BTreeNode {
 std::vector<int> keys;

std::vector<BTreeNode*> children;

bool isLeaf;

BTreeNode(bool leaf) : isLeaf(leaf) {}

};

// Function to create a new B-tree node

BTreeNode* createNode(bool leaf = true) {

return new BTreeNode(leaf);

// Function to search a key in the B-tree

int searchKey(const BTreeNode* node, int key) {

int i = 0;

while (i < node->keys.size() && key > node->keys[i]) {

++i;

return i;

// Function to split a child of the current node

void splitChild(BTreeNode* parent, int index, BTreeNode* child) {

BTreeNode* newChild = createNode(child->isLeaf);

parent->keys.insert(parent->keys.begin() + index, child->keys[t - 1]);

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

 newChild->keys.assign(child->keys.begin() + t, child->keys.end());

child->keys.erase(child->keys.begin() + t, child->keys.end());

if (!child->isLeaf) {

newChild->children.assign(child->children.begin() + t, child->children.end());

child->children.erase(child->children.begin() + t, child->children.end());

// Function to insert a key into the B-tree

void insert(BTreeNode*& root, int key) {

if (root == nullptr) {

root = createNode(true);

root->keys.push_back(key);

} else {

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

BTreeNode* newRoot = createNode(false);

newRoot->children.push_back(root);

splitChild(newRoot, 0, root);

root = newRoot;

insertNonFull(root, key);

// Function to insert a key into a non-full B-tree node

void insertNonFull(BTreeNode* node, int key) {

 int i = node->keys.size() - 1;

if (node->isLeaf) {

node->keys.push_back(0); // Ensure space for the new key

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

node->keys[i + 1] = node->keys[i];

--i;

node->keys[i + 1] = key;

} else {

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

--i;

++i; // Move to the right child

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

splitChild(node, i, node->children[i]);

if (key > node->keys[i]) {

++i;

insertNonFull(node->children[i], key);

// Function to delete a key from the B-tree

void remove(BTreeNode*& root, int key) {

 if (root == nullptr) {

return;

root = removeKey(root, key);

if (root->keys.empty() && !root->isLeaf) {

BTreeNode* newRoot = root->children[0];

delete root;

root = newRoot;

// Function to remove a key from a non-empty B-tree node

BTreeNode* removeKey(BTreeNode* node, int key) {

int index = searchKey(node, key);

if (index < node->keys.size() && node->keys[index] == key) {

if (node->isLeaf) {

// Case 1: The key is in a leaf node

node->keys.erase(node->keys.begin() + index);

} else {

// Case 2: The key is in a non-leaf node

BTreeNode* predecessor = getPredecessor(node, index);

int predecessorKey = predecessor->keys.back();

node->keys[index] = predecessorKey;

node->children[index] = removeKey(node->children[index], predecessorKey);

 }

} else {

// Case 3: The key is not present in this node

bool lastChild = (index == node->keys.size());

BTreeNode* child = node->children[index];

if (child->keys.size() < t) {

// Case 3a: The child has less than t keys

BTreeNode* sibling = (index > 0) ? node->children[index - 1] : nullptr;

if (sibling != nullptr && sibling->keys.size() >= t) {

// Case 3a-i: Borrow a key from the left sibling

borrowFromLeftSibling(node, index);

} else {

BTreeNode* nextSibling = (index < node->children.size() - 1) ? node->children[index + 1]

: nullptr;

if (nextSibling != nullptr && nextSibling->keys.size() >= t) {

// Case 3a-ii: Borrow a key from the right sibling

borrowFromRightSibling(node, index);

} else {

// Case 3a-iii: Merge with a sibling

mergeWithSibling(node, index);

child = node->children[index];

child = removeKey(child, key);

}
 return node;

// Function to borrow a key from the left sibling

void borrowFromLeftSibling(BTreeNode* node, int index) {

BTreeNode* child = node->children[index];

BTreeNode* leftSibling = node->children[index - 1];

// Make space for the borrowed key

child->keys.insert(child->keys.begin(), node->keys[index - 1]);

node->keys[index - 1] = leftSibling->keys.back();

if (!child->isLeaf) {

// Move the child pointer from the left sibling to the child

child->children.insert(child->children.begin(), leftSibling->children.back());

leftSibling->children.pop_back();

// Move the last key from the left sibling to the parent

leftSibling->keys.pop_back();

// Function to borrow a key from the right sibling

void borrowFromRightSibling(BTreeNode* node, int index) {

BTreeNode* child = node->children[index];

BTreeNode* rightSibling = node->children[index + 1];

 // Make space for the borrowed key

child->keys.push_back(node->keys[index]);

node->keys[index] = right

11. Write a C++ program to perform the following operations a)Insertion into an AVL-tree b)
Deletion from an AVL-tree

#include <iostream>

#include <algorithm>

// Define a structure for an AVL tree node

struct AVLNode {

int key;

AVLNode* left;

AVLNode* right;

int height;

};

// Function to create a new AVL tree node

AVLNode* createNode(int key) {

AVLNode* newNode = new AVLNode;

newNode->key = key;

newNode->left = newNode->right = nullptr;

newNode->height = 1; // New node is at height 1

return newNode;

// Function to get the height of a node

int getHeight(AVLNode* node) {

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

// Function to get the balance factor of a node

int getBalanceFactor(AVLNode* node) {

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

// Function to update the height of a node based on the heights of its children

void updateHeight(AVLNode* node) {

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

// Function to perform a right rotation on a given node

AVLNode* rightRotate(AVLNode* y) {

AVLNode* x = y->left;

AVLNode* T2 = x->right;

// Perform rotation

x->right = y;

y->left = T2;

// Update heights

updateHeight(y);

updateHeight(x);
 return x;

// Function to perform a left rotation on a given node

AVLNode* leftRotate(AVLNode* x) {

AVLNode* y = x->right;

AVLNode* T2 = y->left;

// Perform rotation

y->left = x;

x->right = T2;

// Update heights

updateHeight(x);

updateHeight(y);

return y;

// Function to insert a key into an AVL tree

AVLNode* insert(AVLNode* root, int key) {

// Perform standard BST insertion

if (root == nullptr) {

return createNode(key);

if (key < root->key) {

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

} else if (key > root->key) {

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

} else {

// Duplicate keys are not allowed in AVL trees

return root;

// Update height of the current node

updateHeight(root);

// Get the balance factor to check if the node became unbalanced

int balance = getBalanceFactor(root);

// Perform rotations if necessary to restore balance

// Left Left Case

if (balance > 1 && key < root->left->key) {

return rightRotate(root);

// Right Right Case

if (balance < -1 && key > root->right->key) {

return leftRotate(root);

// Left Right Case

if (balance > 1 && key > root->left->key) {

root->left = leftRotate(root->left);

return rightRotate(root);
 }

// Right Left Case

if (balance < -1 && key < root->right->key) {

root->right = rightRotate(root->right);

return leftRotate(root);

// No rotation needed

return root;

// Function to find the node with the minimum key value in a tree

AVLNode* minValueNode(AVLNode* node) {

AVLNode* current = node;

while (current->left != nullptr) {

current = current->left;

return current;

// Function to delete a key from an AVL tree

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

// Perform standard BST delete

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 {

// Node with only one child or no child

if (root->left == nullptr || root->right == nullptr) {

AVLNode* temp = (root->left != nullptr) ? root->left : root->right;

// No child case

if (temp == nullptr) {

temp = root;

root = nullptr;

} else {

// One child case

*root = *temp; // Copy the contents of the non-empty child

delete temp;

} else {

// Node with two children, get the inorder successor

AVLNode* temp = minValueNode(root->right);

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

root->key = temp->key;

// Delete the inorder successor

 root->right = deleteNode(root->right, temp->key);

// If the tree had only one node, return

if (root == nullptr) {

return root;

// Update height of the current node

updateHeight(root);

// Get the balance factor to check if the node became unbalanced

int balance = getBalanceFactor(root);

// Perform rotations if necessary to restore balance

// Left Left Case

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

return rightRotate(root);

// Left Right Case

if (balance > 1 && getBalanceFactor(root->left) < 0) {

root->left = leftRotate(root->left);

return rightRotate(root);

// Right Right Case

if (balance < -1 && getBalanceFactor(root->right) <= 0) {

 return leftRotate(root);

// Right Left Case

if (balance < -1 && getBalanceFactor(root->right) > 0) {

root->right = rightRotate(root->right);

return leftRotate(root);

// No rotation needed

return root;

// Function to perform an inorder traversal of an AVL tree

void inorderTraversal(AVLNode* root) {

if (root != nullptr) {

inorderTraversal(root->left);

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

inorderTraversal(root->right);

int main() {

AVLNode* root = nullptr;

// Insertion

root = insert(root, 10);

root = insert(root, 20);

 root = insert(root, 30);

root = insert(root, 40);

root = insert(root, 50);

root = insert(root, 25);

std::cout << "Inorder traversal after insertion: ";

inorderTraversal(root);

std::cout << std::endl;

// Deletion

root =

12. Write a C++ program to implement all the functions of a dictionary (ADT)

#include <iostream>

#include <list>

#include <vector>

// Define a structure for a key-value pair in the dictionary

struct KeyValuePair {

int key;

std::string value;

KeyValuePair(int k, const std::string& v) : key(k), value(v) {}

};

// Define a class for the dictionary (ADT) using a hash table

class Dictionary {
private:

std::vector<std::list<KeyValuePair>> table;

size_t size;

public:

// Constructor to initialize the hash table with a given size

Dictionary(size_t tableSize) : size(0) {

table.resize(tableSize);

// Function to compute the hash value for a key

size_t hashFunction(int key) const {

return key % table.size();

// Function to insert a key-value pair into the dictionary

void insert(int key, const std::string& value) {

size_t index = hashFunction(key);

KeyValuePair newPair(key, value);

// Check if the key already exists

for (const auto& pair : table[index]) {

if (pair.key == key) {

std::cout << "Key " << key << " already exists. Updating value." << std::endl;

pair.value = value;

return;

}
 }

// Insert the key-value pair

table[index].push_back(newPair);

++size;

std::cout << "Key " << key << " inserted successfully." << std::endl;

// Function to remove a key and its associated value from the dictionary

void remove(int key) {

size_t index = hashFunction(key);

// Find and remove the key-value pair if it exists

auto& bucket = table[index];

for (auto it = bucket.begin(); it != bucket.end(); ++it) {

if (it->key == key) {

bucket.erase(it);

--size;

std::cout << "Key " << key << " removed successfully." << std::endl;

return;

std::cout << "Key " << key << " not found in the dictionary." << std::endl;

// Function to search for a key and return its associated value

 std::string search(int key) const {

size_t index = hashFunction(key);

// Search for the key in the appropriate bucket

for (const auto& pair : table[index]) {

if (pair.key == key) {

return pair.value;

return "Key not found in the dictionary.";

// Function to display the contents of the dictionary

void display() const {

std::cout << "Dictionary Contents:" << std::endl;

for (size_t i = 0; i < table.size(); ++i) {

std::cout << "Bucket " << i << ": ";

for (const auto& pair : table[i]) {

std::cout << "(" << pair.key << ", " << pair.value << ") ";

std::cout << std::endl;

std::cout << "Total size: " << size << std::endl;

};
int main() {

// Create a dictionary with a hash table size of 10

Dictionary dictionary(10);

// Insert key-value pairs into the dictionary

dictionary.insert(1, "One");

dictionary.insert(2, "Two");

dictionary.insert(3, "Three");

dictionary.insert(11, "Eleven");

dictionary.insert(22, "Twenty-Two");

// Display the contents of the dictionary

dictionary.display();

// Search for keys in the dictionary

std::cout << "Value for key 2: " << dictionary.search(2) << std::endl;

std::cout << "Value for key 5: " << dictionary.search(5) << std::endl;

// Remove keys from the dictionary

dictionary.remove(3);

dictionary.remove(5);

// Display the updated contents of the dictionary

dictionary.display();

return 0;