DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

1.Ans:

#include <iostream>
#include <vector>

using namespace std;

//function perform the array into two segments

int partesian(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]);
}
}
swap(arr[i+1], arr[high]);
return i+1;
}

//function to perform quick sort

void quicksort(int arr[], int low, int high)
{
if(low<high){
int pivotIndex = partesian(arr, low, high);

//recursively sort elements before and after the pivot

quicksort(arr, low, pivotIndex-1);
quicksort(arr, pivotIndex+1, high);
}
}

int main()
{
int n;
cin>>n;
int arr[n];

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

cin>>arr[i];
}

quicksort(arr,0,n-1);
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

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

cout<<arr[i]<<" ";
}

return 0;
}

1. Q
#include <iostream>
#include <vector>

using namespace std;

// A utility function to get the maximum value in arr[]

int getMax(vector<int>& arr) {
int max = arr[0];
for (size_t i = 1; i < arr.size(); i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}

// A counting sort of arr[] based on the digit represented by exp.

void countingSort(vector<int>& arr, int exp) {
const int n = arr.size();
vector<int> output(n);
vector<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];
}
}
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

// Main Radix Sort function

void radixSort(vector<int>& arr) {
int max = getMax(arr);

for (int exp = 1; max / exp > 0; exp *= 10) {

countingSort(arr, exp);
}
}

int main() {
int n;
cin >> n;

vector<int> arr(n);

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

cin >> arr[i];
}

radixSort(arr);

cout << "";

for (int num : arr) {
cout << num << " ";
}

return 0;
}

3.Q

#include <iostream>

using namespace std;

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

//for sorted array

int low = 0;

int high = n - 1;

//cout << "\nKey: " <<key<< endl;

//cout << "\nlow: " <<low<< endl;

//cout << "\nhigh: " <<high<< endl;

 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

while (low <= high && key >= arr[low] && key <= arr[high]) {

if (low == high) {

if (arr[low] == key)

return low;

return -1;

// Interpolation formula to estimate the position

int pos = low + ((key - arr[low]) * (high - low) / (arr[high] - arr[low]));

//cout << "\npos: " <<pos;

//cout << "\narr["<<pos<<"]: " <<arr[pos]<< endl;

if (arr[pos] == key)

return pos;

else if (arr[pos] < key)

low = pos + 1;

else

high = pos - 1;

return -1;

int main() {

int n;

//cout << "Enter the number of elements: ";

cin >> n;

int arr[n+1];

//cout << "Enter the elements in sorted order: ";

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

 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

cin >> arr[i];

int key, position;

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

cin >> key;

//cout << "\ninput Key: " <<key<< endl;

position = interpolationSearch(arr, n+1, key);

//cout << "\nPosition: " <<position<< endl;

if (position == -1) {

cout << "Key not found" << endl;

else {

cout << "Element " << key << " found in position " << position+1<< endl;

return 0;

4.Q

#include <iostream>

using namespace std;

int min(int a, int b)

return(a<b?a:b);

}
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

int binarySearch(int arr[], int low, int high, int key) {

while (low <= high) {

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

if (arr[mid] == key)

return mid;

else if (arr[mid] < key)

low = mid + 1;

else

high = mid - 1;

return -1;

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

if (arr[0] == key)

return 0;

int i = 1;

while (i < n && arr[i] <= key)

i *= 2;

return binarySearch(arr, i / 2, std::min(i, n - 1), key); // Use std::min from the <algorithm> header

int main() {

int n;

//cout << "Enter the number of elements: ";

cin >> n;

int arr[n+1];

//cout << "Enter the elements in sorted order: ";

 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

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

cin >> arr[i];

int key;

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

cin >> key;

int position = exponentialSearch(arr, n+1, key);

if (position != -1) {

cout << "Element " << key << " found in position " << position << endl;

} else {

cout << "Key not found" << endl;

return 0;

4.Q

#include <iostream>

using namespace std;

int min(int a, int b)

return(a<b?a:b);

int binarySearch(int arr[], int low, int high, int key) {

while (low <= high) {

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

if (arr[mid] == key)

return mid;
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

else if (arr[mid] < key)

low = mid + 1;

else

high = mid - 1;

return -1;

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

if (arr[0] == key)

return 0;

int i = 1;

while (i < n && arr[i] <= key)

i *= 2;

return binarySearch(arr, i / 2, std::min(i, n - 1), key); // Use std::min from the <algorithm> header

int main() {

int n;

//cout << "Enter the number of elements: ";

cin >> n;

int arr[n+1];

//cout << "Enter the elements in sorted order: ";

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

cin >> arr[i];

int key;
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

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

cin >> key;

int position = exponentialSearch(arr, n+1, key);

if (position != -1) {

cout << "Element " << key << " found in position " << position << endl;

} else {

cout << "Key not found" << endl;

return 0;

5.q

#include <iostream>

using namespace std;

// Definition of a Binary Search Tree node

struct Node {

int data;

Node* left;

Node* right;

Node(int val) : data(val), left(nullptr), right(nullptr) {}

};

// Function to insert a new node into the BST

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

if (root == nullptr) {

return new Node(val);

 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

if (val < root->data) {

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

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

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

return root;

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

Node* findMin(Node* root) {

while (root->left != nullptr) {

root = root->left;

return root;

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

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

if (root == nullptr) {

return root;

if (key < root->data) {

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

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

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

} else {

if (root->left == nullptr) {

Node* temp = root->right;

delete root;

return temp;
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

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

Node* temp = root->left;

delete root;

return temp;

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

root->data = temp->data;

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

return root;

// Function to perform in-order traversal

void inOrder(Node* root) {

if (root == nullptr) return;

inOrder(root->left);

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

inOrder(root->right);

// Function to perform pre-order traversal

void preOrder(Node* root) {

if (root == nullptr) return;

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

preOrder(root->left);

preOrder(root->right);

// Function to perform post-order traversal

void postOrder(Node* root) {

if (root == nullptr) return;

 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

postOrder(root->left);

postOrder(root->right);

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

int main() {

Node* root = nullptr;

int n;

cin >> n;

cout << "";

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

int val;

cin >> val;

root = insert(root, val);

cout << "";

inOrder(root);

cout << endl;

cout << "";

preOrder(root);

cout << endl;

cout << "";

postOrder(root);

cout << endl;

// Delete 6 and perform in-order traversal

 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

root = deleteNode(root, 6);

cout << "";

inOrder(root);

cout << endl;

// Insert 8 and perform in-order traversal

root = insert(root, 8);

cout << "";

inOrder(root);

cout << endl;

// Delete 5 and perform in-order traversal

root = deleteNode(root, 5);

cout << "";

inOrder(root);

cout << endl;

return 0;

6.q

#include <iostream>

using namespace std;

// Definition of a Binary Search Tree node

struct Node {

int data;

Node* left;

Node* right;

Node(int val) : data(val), left(nullptr), right(nullptr) {}

};
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

// Function to insert a new node into the BST

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

if (root == nullptr) {

return new Node(val);

if (val < root->data) {

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

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

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

return root;

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

Node* findMin(Node* root) {

while (root->left != nullptr) {

root = root->left;

return root;

// Function to perform in-order traversal

void inOrder(Node* root) {

if (root == nullptr) return;

inOrder(root->left);

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

inOrder(root->right);

int main() {
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

Node* root = nullptr;

int n;

cin >> n;

cout << "";

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

int val;

cin >> val;

root = insert(root, val);

cout << "";

inOrder(root);

cout << endl;

return 0;

7.q

#include <iostream>

using namespace std;

// Structure for an AVL tree node

struct AVLNode {

int data;

AVLNode* left;

AVLNode* right;

int height;

};

// Function to calculate the height of a node

int height(AVLNode* node) {

 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

if (node == nullptr) return 0;

return node->height;

// Function to calculate the balance factor of a node

int balanceFactor(AVLNode* node) {

if (node == nullptr) return 0;

return height(node->left) - height(node->right);

// Function to create a new AVL tree node

AVLNode* createNode(int key) {

AVLNode* newNode = new AVLNode;

newNode->data = key;

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

newNode->height = 1;

return newNode;

// Function to perform a right rotation

AVLNode* rightRotate(AVLNode* y) {

AVLNode* x = y->left;

AVLNode* 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;
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

// Function to perform a left rotation

AVLNode* leftRotate(AVLNode* x) {

AVLNode* y = x->right;

AVLNode* T2 = y->left;

y->left = x;

x->right = T2;

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

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

return y;

// Function to insert a key into the AVL tree

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

if (root == nullptr) return createNode(key);

if (key < root->data) {

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

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

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

} else {

return root;

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

int balance = balanceFactor(root);

 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

if (balance > 1) {

if (key < root->left->data) {

return rightRotate(root);

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

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

return rightRotate(root);

if (balance < -1) {

if (key > root->right->data) {

return leftRotate(root);

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

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

return leftRotate(root);

return root;

// Function to perform in-order traversal

void inOrderTraversal(AVLNode* root) {

if (root == nullptr) return;

inOrderTraversal(root->left);

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

inOrderTraversal(root->right);

}
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

// Function to perform pre-order traversal

void preOrderTraversal(AVLNode* root) {

if (root == nullptr) return;

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

preOrderTraversal(root->left);

preOrderTraversal(root->right);

// Function to perform post-order traversal

void postOrderTraversal(AVLNode* root) {

if (root == nullptr) return;

postOrderTraversal(root->left);

postOrderTraversal(root->right);

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

int main() {

AVLNode* root = nullptr;

int n, num;

cin >> n;

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

cin >> num;

root = insert(root, num);

preOrderTraversal(root);

cout << endl;

 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

inOrderTraversal(root);

cout << endl;

postOrderTraversal(root);

cout << endl;

return 0;

8.Q

#include <iostream>

using namespace std;

const int ORDER = 3;

// Structure for a B-tree node

struct BTreeNode {

int keys[ORDER - 1]; // Data elements

BTreeNode* children[ORDER]; // Child pointers

int numKeys; // Number of keys

};

// Function to create a new B-tree node

BTreeNode* createNode(int key) {

BTreeNode* newNode = new BTreeNode;

newNode->keys[0] = key;

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

newNode->children[i] = nullptr;

}
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

newNode->numKeys = 1;

return newNode;

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

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

if (root == nullptr) {

return createNode(key);

if (root->numKeys < ORDER - 1) {

int i = root->numKeys - 1;

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

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

i--;

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

root->numKeys++;

} else {

int i = root->numKeys - 1;

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

i--;

if (root->children[i + 1] != nullptr) {

root->children[i + 1] = insert(root->children[i + 1], key);

} else {

root->children[i + 1] = createNode(key);

}
 DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

return root;

// Function to traverse the B-tree and display the contents

void traverseBTree(BTreeNode* root) {

if (root != nullptr) {

for (int i = 0; i < root->numKeys; i++) {

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

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

traverseBTree(root->children[i]);

int main() {

BTreeNode* root = nullptr;

int n, key;

n = 10;

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

cin >> key;

root = insert(root, key);

traverseBTree(root);

cout << endl;

return 0;

}
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03