Department of Electrical Engineering Autumn 2025
EEO 101: DATA STRUCTURES
Worksheet – 7
Name: Anuj Kumar Gupta
Enrollment: 24115026
Department: Department of Electrical Engineering
Year: 2nd
Batch: B
Q1. Write a function to find kth node in a linked list represented by a binary tree. Using
this function write another function to delete Kth node of the list.
CODE:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *left; // unused
struct Node *right; // acts as 'next' pointer
} Node;
// Function to create a new node
Node *createNode(int data)
{
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to find k-th node in linked list (1-based)
Node *findKthNode(Node *head, int k)
{
int count = 1;
Node *temp = head;
while (temp != NULL && count < k)
{
temp = temp->right;
count++;
}
if (count == k && temp != NULL)
return temp;
else
return NULL; // k is out of range
}
// Function to delete k-th node from the linked list
Node *deleteKthNode(Node *head, int k)
{
if (head == NULL)
return NULL;
// Case 1: Deleting the head
if (k == 1)
{
Node *temp = head;
head = head->right;
free(temp);
return head;
}
// Find (k-1)th node
Node *prev = findKthNode(head, k - 1);
if (prev == NULL || prev->right == NULL)
return head; // invalid k, no deletion
// Delete kth node
Node *toDelete = prev->right;
prev->right = toDelete->right;
free(toDelete);
return head;
}
// Function to print the linked list
void printList(Node *head)
{
Node *temp = head;
while (temp != NULL)
{
printf("%d -> ", temp->data);
temp = temp->right;
}
printf("NULL\n");
}
// Test example
int main()
{
// Create a linked list (represented by right pointers)
Node *head = createNode(10);
head->right = createNode(20);
head->right->right = createNode(30);
head->right->right->right = createNode(40);
head->right->right->right->right = createNode(50);
printf("Original list:\n");
printList(head);
int k = 3;
Node *kth = findKthNode(head, k);
if (kth)
printf("The %dth node is: %d\n", k, kth->data);
else
printf("%dth node not found.\n", k);
// Delete the kth node
head = deleteKthNode(head, k);
printf("\nAfter deleting %dth node:\n", k);
printList(head);
return 0;
}
Comments
//Implemented findKthnode and deleteKthnode
OUTPUT
Q2. Use the functions developed in 1 to implement the Josephus Problem.
CODE
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
Node* findKthNode(Node* head, int k) {
int count = 1;
Node* temp = head;
while (temp != NULL && count < k) {
temp = temp->right;
count++;
}
if (count == k && temp != NULL)
return temp;
else
return NULL;
}
Node* deleteKthNode(Node* head, int k) {
if (head == NULL)
return NULL;
if (k == 1) {
Node* temp = head;
head = head->right;
free(temp);
return head;
}
Node* prev = findKthNode(head, k - 1);
if (prev == NULL || prev->right == NULL)
return head;
Node* toDelete = prev->right;
prev->right = toDelete->right;
free(toDelete);
return head;
}
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->right;
}
printf("NULL\n");
}
Node* createCircularList(int n) {
Node* head = createNode(1);
Node* temp = head;
for (int i = 2; i <= n; i++) {
temp->right = createNode(i);
temp = temp->right;
}
temp->right = head;
return head;
}
int josephus(int n, int k) {
Node* head = createCircularList(n);
Node* ptr = head;
while (ptr->right != ptr) {
for (int count = 1; count < k - 1; count++)
ptr = ptr->right;
Node* toDelete = ptr->right;
printf("Eliminated: %d\n", toDelete->data);
ptr->right = toDelete->right;
free(toDelete);
ptr = ptr->right;
}
int survivor = ptr->data;
free(ptr);
return survivor;
}
int main() {
int n = 7; // number of people
int k = 3; // eliminate every 3rd person
printf("Josephus Problem (n = %d, k = %d)\n", n, k);
int survivor = josephus(n, k);
printf("\nSurvivor is: %d\n", survivor);
return 0;
}
Comments
// Implemented Josephus problem using deletekthnode and findkthnode
OUTPUT
Q3. Write a function to create a Max Heap Tree
CODE
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
void heapify(int arr[], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
void buildMaxHeap(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}
void printHeap(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {4, 10, 3, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printHeap(arr, n);
buildMaxHeap(arr, n);
printf("Max Heap array:\n");
printHeap(arr, n);
return 0;
}
Comments
// Created max heap
OUTPUT
Q4. Write a function to create a Min Heap Tree
CODE
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void heapify(int arr[], int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest])
smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
swap(&arr[i], &arr[smallest]);
heapify(arr, n, smallest);
}
}
void buildMinHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}
void printHeap(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {4, 10, 3, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printHeap(arr, n);
buildMinHeap(arr, n);
printf("Min Heap array:\n");
printHeap(arr, n);
return 0;
}
Comments
// Created min heap
OUTPUT
Q5. Write a function delete_root( ) to delete the root of a Max heap tree
CODE
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
void buildMaxHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}
int delete_root(int arr[], int n) {
if (n <= 0)
return n;
arr[0] = arr[n - 1];
n = n - 1;
heapify(arr, n, 0);
return n;
}
void printHeap(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {10, 5, 3, 4, 1};
int n = sizeof(arr) / sizeof(arr[0]);
buildMaxHeap(arr, n);
printf("Max Heap:\n");
printHeap(arr, n);
n = delete_root(arr, n);
printf("After deleting root:\n");
printHeap(arr, n);
return 0;
}
Comments
// Implemented delete_root function
OUTPUT
Q6. Making use of the functions developed in 3,4 and 5 write a function to implement Heap
sort algorithm to sort a given array. Your function should receive a flag SORT to decide
ascending order or descending order sorting as follows
SORT = 1 Ascending order SORT = 0 Descending order
CODE:
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void maxHeapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
maxHeapify(arr, n, largest);
}
}
void minHeapify(int arr[], int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest])
smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
swap(&arr[i], &arr[smallest]);
minHeapify(arr, n, smallest);
}
}
void buildMaxHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
maxHeapify(arr, n, i);
}
void buildMinHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
minHeapify(arr, n, i);
}
void heapSort(int arr[], int n, int SORT) {
if (SORT == 1)
buildMaxHeap(arr, n);
else
buildMinHeap(arr, n);
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
if (SORT == 1)
maxHeapify(arr, i, 0);
else
minHeapify(arr, i, 0);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr1[] = {12, 11, 13, 5, 6, 7};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
printf("Original array:\n");
printArray(arr1, n1);
heapSort(arr1, n1, 1);
printf("Sorted in Ascending order:\n");
printArray(arr1, n1);
int arr2[] = {12, 11, 13, 5, 6, 7};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
heapSort(arr2, n2, 0);
printf("Sorted in Descending order:\n");
printArray(arr2, n2);
return 0;
}
Comments
//Implemented solution to given problem
OUTPUT