Data Structures Lab: Assignment 2 [Each Q- 20 Marks]
1.Program Statement: Construct a binary search tree for the data 5, 1, 7,
6, 3, 9, 6, 17, 64, 100, 2, 4 .
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
};
// Create new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Insert into BST
struct Node* insert(struct Node* root, int data) {
if (root == NULL)
return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else
root->right = insert(root->right, data);
return root;
}
// Inorder traversal
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
int values[] = {5, 1, 7, 6, 3, 9, 6, 17, 64, 100, 2, 4};
int n = sizeof(values) / sizeof(values[0]);
struct Node* root = NULL;
for (int i = 0; i < n; i++)
root = insert(root, values[i]);
printf("Inorder traversal of BST: ");
inorder(root);
return 0;
}
Output:
2.Program Statement: Describe the binary search algorithm for
searching the element 11 in the data: 8, 15, 18,19, 23, 43, 55, 67 .
#include <stdio.h>
int binarySearch(int arr[], int size, int key) {
int low = 0, high = size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid; // found
else if (key < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1; // not found
}
int main() {
int arr[] = {8, 15, 18, 19, 23, 43, 55, 67};
int size = sizeof(arr) / sizeof(arr[0]);
int key = 11;
int result = binarySearch(arr, size, key);
if (result != -1)
printf("Element %d found at index %d\n", key, result);
else
printf("Element %d not found in the array.\n", key);
return 0;
}
3.Program Statement: Explain how the bubble sort algorithm works for
the list of numbers 11, 35, 67, 26, 121,45,11, 39, 113.
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
int step = 1;
for (i = 0; i < n - 1; i++) {
printf("Pass %d: ", step++);
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
for (int k = 0; k < n; k++)
printf("%d ", arr[k]);
printf("\n");
}
}
int main() {
int arr[] = {11, 35, 67, 26, 121, 45, 11, 39, 113};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
return 0;
}
Output:
4.Program Statement: Write a program to generate n random numbers
and to find the maximum minimum number and their sum.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
int n, i;
printf("Enter the number of random elements: ");
scanf("%d", &n);
int arr[n];
srand(time(NULL)); // Seed the random number generator
printf("Generated numbers: ");
for (i = 0; i < n; i++) {
arr[i] = rand() % 100; // Random number between 0 and 99
printf("%d ", arr[i]);
}
int max = arr[0], min = arr[0], sum = 0;
for (i = 0; i < n; i++) {
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
sum += arr[i];
}
printf("\nMaximum = %d\n", max);
printf("Minimum = %d\n", min);
printf("Sum = %d\n", sum);
return 0;
}
Output:
5.Program Statement: Sort the following list of elements using quick
sort algorithm 53, 81, 23, 28, 65, 43, 52, 95, 22.
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(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);
}
void quickSort(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);
}
}
int main() {
int arr[] = {53, 81, 23, 28, 65, 43, 52, 95, 22};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
quickSort(arr, 0, n - 1);
printf("\nSorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Output:
