ADVANCED PROGRAMMING PRACTICES ASSIGNMENT 14

Vignesh M Shinde

MRH2025029

[Link] 1st year

8/10/25

1. Using linked list representation, create a binary search tree for: 50, 10, 20, 30, 5, 90,
80, 100, 85 Write a menu-driven program for the functions to traverse the tree in
preorder, postorder and inorder traversal.
SOLUTION:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left, *right;
};
struct node* createNode(int data) {
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
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;
}
void inorder(struct node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
void preorder(struct node* root) {
 if (root) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct node* root) {
if (root) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
int main() {
int arr[] = {50,10,20,30,5,90,80,100,85}, n = 9;
struct node* root = NULL;
for (int i = 0; i < n; i++) root = insert(root, arr[i]);
int choice;
while (1) {
printf("\[Link] [Link] [Link] [Link]\n");
scanf("%d", &choice);
switch (choice) {
case 1: inorder(root); break;
case 2: preorder(root); break;
case 3: postorder(root); break;
case 4: exit(0);
}
}
}

2. In program 1, add the functions for search, insert and delete an element from the tree.
SOLUTION:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left, *right;
};
struct node* createNode(int data) {
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
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 if (data > root->data) root->right = insert(root->right, data);
return root;
}
struct node* minValueNode(struct node* node) {
struct node* current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
struct node* deleteNode(struct node* root, int key) {
if (root == NULL) 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 == NULL) {
struct node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct node* temp = root->left;
free(root);
return temp;
}
struct node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
 }
return root;
}
struct node* search(struct node* root, int key) {
if (root == NULL || root->data == key) return root;
if (key < root->data) return search(root->left, key);
return search(root->right, key);
}
void inorder(struct node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
int arr[] = {50,10,20,30,5,90,80,100,85}, n = 9;
struct node* root = NULL;
for (int i = 0; i < n; i++) root = insert(root, arr[i]);
int choice, val;
while (1) {
printf("\[Link] [Link] [Link] [Link] [Link]\n");
scanf("%d", &choice);
switch (choice) {
case 1: inorder(root); break;
case 2: scanf("%d",&val); root = insert(root,val); break;
case 3: scanf("%d",&val); root = deleteNode(root,val); break;
case 4: scanf("%d",&val);
if (search(root,val)) printf("Found\n");
else printf("Not Found\n");
break;
case 5: exit(0);
}
}
}
3. Using the tree created in program 1, write a function to give the level for the user
given element. (assuming root of the tree is at level 0)
SOLUTION:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left, *right;
};
struct node* createNode(int data) {
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
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 if (data > root->data) root->right = insert(root->right, data);
return root;
}
int getLevel(struct node* root, int data, int level) {
if (root == NULL) return -1;
if (root->data == data) return level;
if (data < root->data) return getLevel(root->left, data, level + 1);
else return getLevel(root->right, data, level + 1);
}
int main() {
int arr[] = {50,10,20,30,5,90,80,100,85}, n = 9;
struct node* root = NULL;
for (int i = 0; i < n; i++) root = insert(root, arr[i]);
int x;
scanf("%d", &x);
int level = getLevel(root, x, 0);
if (level != -1) printf("Level: %d", level);
else printf("Not Found");
}
4. Write a program to find the largest element in BST created in program-1.
SOLUTION:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left, *right;
};
struct node* createNode(int data) {
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
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;
}
int largest(struct node* root) {
while (root->right != NULL)
root = root->right;
return root->data;
}
int main() {
int arr[] = {50,10,20,30,5,90,80,100,85}, n = 9;
struct node* root = NULL;
for (int i = 0; i < n; i++) root = insert(root, arr[i]);
printf("Largest: %d", largest(root));
}

5. Create Heap tree for 50, 10, 20, 30, 5, 90, 80, 100, 85
Perform the traversing on the Heap Tree.
SOLUTION:
#include <stdio.h>
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void buildHeap(int arr[], int n) {
for (int i = n/2 - 1; i >= 0; i--)
heapify(arr, n, i);
}
void inorder(int arr[], int n, int i) {
if (i < n) {
inorder(arr, n, 2*i + 1);
printf("%d ", arr[i]);
inorder(arr, n, 2*i + 2);
}
}
void preorder(int arr[], int n, int i) {
if (i < n) {
printf("%d ", arr[i]);
preorder(arr, n, 2*i + 1);
preorder(arr, n, 2*i + 2);
}
}
void postorder(int arr[], int n, int i) {
if (i < n) {
postorder(arr, n, 2*i + 1);
postorder(arr, n, 2*i + 2);
printf("%d ", arr[i]);
}
}
int main() {
int arr[] = {50,10,20,30,5,90,80,100,85}, n = 9;
buildHeap(arr, n);
printf("\nInorder: "); inorder(arr, n, 0);
printf("\nPreorder: "); preorder(arr, n, 0);
printf("\nPostorder: "); postorder(arr, n, 0);
}