GROUP A-1

Write a Python program to manage the borrowing records of books in a

library. Implement the following functionalities:
• Compute the average number of books borrowed by all library
members.
• Find the book with the highest and lowest number of borrowings in
the library.
• Count the number of members who have not borrowed any books
(denoted by a borrow count of 0).
• Display the most frequently borrowed book (i.e., the mode of borrow
counts). After performing, determine the time and Space complexity of
each operation

from collections import Counter

# Sample data structure

# Each member has a list of borrowed books
borrow_records = {
'Member1': ['BookA', 'BookB', 'BookC'],
'Member2': [],
'Member3': ['BookA'],
'Member4': ['BookA', 'BookC'],
'Member5': [],
'Member6': ['BookB', 'BookC', 'BookC', 'BookC']
}

def compute_average_borrowings(records):
total_books = sum(len(books) for books in records.values())
total_members = len(records)
average = total_books / total_members if total_members > 0 else 0
return average

def book_borrow_counts(records):
 counter = Counter ()
for books in records.values():
counter.update(books)
return counter

def highest_lowest_borrowed(counter):
if not counter:
return None, None
most = counter.most_common(1)[0]
least = min(counter.items(), key=lambda x: x[1])
return most, least

def count_non_borrowers(records):
return sum(1 for books in records.values() if len(books) == 0)

def most_frequent_book(counter):
if not counter:
return None
mode_count = max(counter.values())
modes = [book for book, count in counter.items() if count == mode_count]
return modes

# Execution
average = compute_average_borrowings(borrow_records)
counter = book_borrow_counts(borrow_records)
highest, lowest = highest_lowest_borrowed(counter)
non_borrowers = count_non_borrowers(borrow_records)
most_frequent = most_frequent_book(counter)

# Output
print (f"Average number of books borrowed: {average:.2f}")
print (f"Book with highest borrowings: {highest}")
print (f"Book with lowest borrowings: {lowest}")
print (f"Number of members who have not borrowed any books:
{non_borrowers}")
print (f"Most frequently borrowed book(s): {most_frequent}")
 GROUP A-2
In an e-commerce system, customer account IDs are stored in a list, and you
are tasked with
Writing a program that implements the following:
•LinearSearch:Check if a particular customer account ID exists in the list.

•Binary Search: Implement Binary search to find if a customer account ID

exists,
Improving the search efficiency over the basic linear

linear_search(account_list, target_id):
for account_id in account_list:
if account_id == target_id:
return True # Found
return False # Not found

# Sample list of customer account IDs

customer_account_ids = ['C101', 'C102', 'C103', 'C104', 'C105']

# ID to search for
target = 'C103'

# Check if the ID exists

if linear_search(customer_account_ids, target):
print (f"Customer account ID {target} exists in the list.")
else:
print (f"Customer account ID {target} does NOT exist in the list.")

def binary_search(account_list, target_id):

low = 0
high = len(account_list) - 1

while low <= high:

 mid = (low + high) // 2
mid_id = account_list[mid]

if mid_id == target_id:
return True # Found
elif mid_id < target_id:
low = mid + 1
else:
high = mid - 1

return False # Not found

# Sample sorted list of customer account IDs

customer_account_ids = ['C101', 'C102', 'C103', 'C104', 'C105']

# ID to search
target = 'C103'

# Check if the ID exists

if binary_search(customer_account_ids, target):
print(f"Customer account ID {target} exists in the list.")
else:
print(f"Customer account ID {target} does NOT exist in the list.")
 GROUP A–3
Inacompany, employee salaries are storedinalistasfloating-pointnumbers.
Writea
Pythonprogramthatsortstheemployeesalariesinascendingorderusingthefollo
wingtwo algorithms:
•SelectionSort:Sortthesalariesusingtheselectionsortalgorithm.
•BubbleSort:Sortthesalariesusingthebubblesortalgorithm.
Aftersortingthesalaries,the programs
houlddisplaytopfivehighestsalariesinthecompany

Sorting Algorithms Explained

Selection Sort

• Repeatedly finds the smallest element and moves it to the front.

• Simple but not very efficient for large datasets.

python
def selection_sort(salaries):
for i in range(len(salaries)):
min_index = i
for j in range (i+1, len(salaries)):
if salaries[j] < salaries[min_index]:
min_index = j
salaries[i], salaries[min_index] = salaries[min_index], salaries[i]
return salaries

Bubble Sort

• Repeatedly compares adjacent elements and swaps them if they're in

the wrong order.
• Intuitive and easy to implement.

python
def bubble_sort(salaries):
n = len(salaries)
for i in range(n):
for j in range (0, n-i-1):
 if salaries[j] > salaries[j+1]:
salaries[j], salaries[j+1] = salaries[j+1], salaries[j]
return salaries

Display Top Five Salaries

Once sorted, you can display the five highest like so:

python
def top_five_highest(salaries):
return salaries [-5:] # last 5 elements after ascending sort

Combine everything:

python
salaries = [56000.75, 42000.50, 78000.00, 89000.25, 62000.80, 51000.30,
99000.00]

sorted_salaries = selection_sort(salaries.copy())
print ("Top 5 highest salaries (Selection Sort):",
top_five_highest(sorted_salaries))

sorted_salaries = bubble_sort(salaries.copy())
print ("Top 5 highest salaries (Bubble Sort):",
top_five_highest(sorted_salaries))

GROUP B-1
Implementing a real-time undo/redo system for M a text editing application
using a Stack data
Implementing a real-time undo/redo system for a text editing application
using a Stack data
structure. The system should support the following operations:
• Make a Change: A new change to the document is made.
• Undo Action: Revert the most recent change and store it for potential
redo.
• Redo Action: Reapply the most recently undone action.
• Display Document State: Show the current state of the document after
undoing or redoing an action

class TextEditor:
def __init__(self):
self.undo_stack = []
self.redo_stack = []
self.current_state = ""

def make_change(self, new_text):

self.undo_stack.append(self.current_state)
self.current_state = new_text
self.redo_stack.clear() # Clear redo history on new change
print ("Change made.")

def undo_action(self):
if not self.undo_stack:
print ("Nothing to undo.")
return
self.redo_stack.append(self.current_state)
self.current_state = self.undo_stack.pop()
print ("Undo performed.")

def redo_action(self):
 if not self.redo_stack:
print ("Nothing to redo.")
return
self.undo_stack.append(self.current_state)
self.current_state = self.redo_stack.pop()
print ("Redo performed.")

def display_document_state(self):
print (f" Current Document State:\n{self.current_state}")
editor = TextEditor()

editor.make_change("Hello")
editor.make_change("Hello, World!")
editor.display_document_state()

editor.undo_action()
editor.display_document_state()

editor.redo_action()
editor.display_document_state()

#OUTPUT
Change made.
Change made.
Current Document State:
Hello, World!
Undo performed.
Current Document State:
Hello
Redo performed.
Current Document State:
Hello, World!
GROUP B-2
Implement a real-time event processing system using a Queue data
structure. The system
should support the following features:
• Add an Event: When a new event occurs, it should be added to the event
queue.
• Process the Next Event: The system should process and remove the
event that has been in the queue the longest.
• Display Pending Events: Show all the events currently waiting to be
processed.
• Cancel an Event: An event can be canceled if it has not been processed.

from collections import deque

class EventProcessor:
def __init__(self):
self.event_queue = deque ()

def add_event(self, event):

self.event_queue.append(event)
print (f" Event added: {event}")

def process_next_event(self):
if not self.event_queue:
print (" No events to process.")
return
event = self.event_queue.popleft()
print (f"Processed event: {event}")

def display_pending_events(self):
if not self.event_queue:
print (" No pending events.")
else:
 print (" Pending Events:")
for idx, event in enumerate (self.event_queue, 1):
print(f"{idx}. {event}")

def cancel_event(self, event_to_cancel):

if event_to_cancel not in self.event_queue:
print(f" Event '{event_to_cancel}' not found or already processed.")
return
temp_queue = deque()
canceled = False
while self.event_queue:
event = self.event_queue.popleft()
if event == event_to_cancel and not canceled:
print(f"Canceled event: {event}")
canceled = True
else:
temp_queue.append(event)
self.event_queue = temp_queue
ep = EventProcessor()
ep.add_event("User Login")
ep.add_event("File Upload")
ep.add_event("Data Backup")
ep.display_pending_events()
ep.cancel_event("File Upload")
ep.display_pending_events()
ep.process_next_event()
ep.display_pending_events()

#OUT PUT
Event added: User Login
Event added: File Upload
Event added: Data Backup
Pending Events:
1. User Login
2. File Upload
3. Data Backup
Canceled event: File Upload
Pending Events:
1. User Login
2. Data Backup
Processed event: User Login
Pending Events:
1. Data Backup

Group C - Hashing
Implement a hash table of size 10 and use the division method as a hash
function. In case of
a collision, use chaining. Implement the following operations:
• Insert(key): Insert key-value pairs into the hash table.
• Search(key): Search for the value associated with a given key.
• Delete(key): Delete a key-value pair from the hash table

hash_index = key % 10

class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[ ] for _ in range(size)] # Each slot is a list for chaining

def _hash(self, key):

return key % self.size

def insert(self, key, value):

index = self._hash(key)
# Check if key already exists, update if found
for pair in self.table[index]:
if pair[0] == key:
pair[1] = value
return
# Otherwise, append new key-value pair
self.table[index].append([key, value])

def search(self, key):

index = self._hash(key)
for pair in self.table[index]:
if pair[0] == key:
return pair[1]
 return None # Key not found

def delete(self, key):

index = self._hash(key)
for i, pair in enumerate(self.table[index]):
if pair[0] == key:
del self.table[index][i]
return True
return False # Key not found

def display(self):
for i, chain in enumerate(self.table):
print(f"Index {i}: {chain}")

#output

Search 25: Banana

Search 99: None
Search 25 after deletion: None
Index 0: []
Index 1: []
Index 2: []
Index 3: []
Index 4: []
Index 5: [[15, 'Apple'], [35, 'Cherry'], [5, 'Date']]
Index 6: []
Index 7: []
Index 8: []
Index 9: []

Design and implement a hash table of fixed size. Use the division method for
the hash
function and resolve collisions using linear probing. Allow the user to perform
the following operations:
• Insert a key
• Search for a key
• Delete a key
• Display the table

Hash Function: index = key % size

Collision Resolution: Linear probing (search next available slot)

Special Note: We use a sentinel value (None) for empty slots and a special
marker ("DELETED") to indicate deleted entries.

class LinearProbingHashTable:
def __init__(self, size=10):
self.size = size
self.table = [None] * size

def _hash(self, key):

return key % self.size

def insert(self, key):

index = self._hash(key)
for i in range(self.size):
probe_index = (index + i) % self.size
if self.table[probe_index] is None or self.table[probe_index] ==
"DELETED":
self.table[probe_index] = key
return True
print("Hash Table is full. Cannot insert.")
return False
 def search(self, key):
index = self._hash(key)
for i in range(self.size):
probe_index = (index + i) % self.size
if self.table[probe_index] is None:
return False
if self.table[probe_index] == key:
return True
return False

def delete(self, key):

index = self._hash(key)
for i in range(self.size):
probe_index = (index + i) % self.size
if self.table[probe_index] is None:
return False
if self.table[probe_index] == key:
self.table[probe_index] = "DELETED"
return True
return False

def display(self):
print("Hash Table Contents:")
for i, val in enumerate(self.table):
print(f"Index {i}: {val}")

ht = LinearProbingHashTable()

ht.insert(10)
ht.insert(20)
ht.insert(30)
ht.insert(25) # Will cause collision with 10 if size is 10
print("Search 20:", ht.search(20)) # True
print("Search 99:", ht.search(99)) # False

ht.delete(20)
print("Search 20 after deletion:", ht.search(20)) # False

ht.display()

Search 20: True

Search 99: False
Search 20 after deletion: False
Hash Table Contents:
Index 0: 10
Index 1: 20
Index 2: 30
Index 3: 25
Index 4: None
Index 5: None
Index 6: None
Index 7: None
Index 8: None
Index 9: None

Implement a hash table with extendible hashing. The hash table should
dynamically expand
when the number of keys in a bucket exceeds a certain threshold. Perform
the following operations:
• Insert(key): Insert key-value pairs into the hash table
• Search(key): Search for the value associated with a given key
• Delete(key): Delete a key-value pair from the hash table

class Bucket:
def __init__(self, depth, size_limit):
self.local_depth = depth
self.size_limit = size_limit
self.items = {}

def is_full(self):
return len(self.items) >= self.size_limit

def insert(self, key, value):

self.items[key] = value

def delete(self, key):

if key in self.items:
del self.items[key]

def search(self, key):

return self.items.get(key, None)

class ExtendibleHashTable:
def __init__(self, bucket_size=2):
self.global_depth = 1
self.bucket_size = bucket_size
self.directory = [Bucket(depth=1, size_limit=bucket_size) for _ in
range(2)]
def _hash(self, key):
return hash(key) & ((1 << self.global_depth) - 1)

def insert(self, key, value):

index = self._hash(key)
bucket = self.directory[index]

if not bucket.is_full():
bucket.insert(key, value)
else:
if bucket.local_depth == self.global_depth:
self._double_directory()

self._split_bucket(index)
self.insert(key, value) # Retry insertion

def _double_directory(self):
self.global_depth += 1
new_directory = []
for bucket in self.directory:
new_directory.append(bucket)
new_directory.append(bucket)
self.directory = new_directory

def _split_bucket(self, index):

old_bucket = self.directory[index]
new_depth = old_bucket.local_depth + 1
old_bucket.local_depth = new_depth
new_bucket = Bucket(depth=new_depth, size_limit=self.bucket_size)

# Redistribute keys
keys_to_redistribute = list(old_bucket.items.items())
old_bucket.items.clear()
 for key, value in keys_to_redistribute:
new_index = hash(key) & ((1 << self.global_depth) - 1)
if (hash(key) >> (new_depth - 1)) & 1:
new_bucket.insert(key, value)
else:
old_bucket.insert(key, value)

# Update directory pointers

for i in range(len(self.directory)):
if self.directory[i] == old_bucket:
if (i >> (new_depth - 1)) & 1:
self.directory[i] = new_bucket

def search(self, key):

index = self._hash(key)
return self.directory[index].search(key)

def delete(self, key):

index = self._hash(key)
self.directory[index].delete(key)

#output
ht = ExtendibleHashTable(bucket_size=2)

ht.insert("apple", 1)
ht.insert("banana", 2)
ht.insert("cherry", 3)
ht.insert("date", 4)

print(ht.search("banana")) # Output: 2
ht.delete("banana")
print(ht.search("banana")) # Output: None

Group D: Graphs and Trees

1. Consider a particular area in your city. Note the popular locations A, B,

C . . . in that area. Assume these locations represent nodes of a graph.
 If there is a route between two locations, it is represented as
connections between nodes. Find out the sequence in which you will
visit these locations, starting from (say A) using (i) BFS and (ii) DFS.
Represent a given graph using an adjacency matrix to perform DFS and
an adjacency list to perform BFS.

#include <stdio.h>
#include <stdlib.h>

#define MAX 5

// Mapping: A=0, B=1, C=2, D=3, E=4

char locations[MAX] = {'A', 'B', 'C', 'D', 'E'};

// ---------------- DFS using Adjacency Matrix ----------------

int adjMatrix[MAX][MAX] = {
{0, 1, 1, 0, 0}, // A
{1, 0, 0, 1, 0}, // B
{1, 0, 0, 0, 1}, // C
{0, 1, 0, 0, 0}, // D
{0, 0, 1, 0, 0} // E
};

int visitedDFS[MAX];

void DFS(int node) {

visitedDFS[node] = 1;
printf("%c ", locations[node]);
for (int i = 0; i < MAX; i++) {
if (adjMatrix[node][i] == 1 && !visitedDFS[i]) {
DFS(i);
}
}
}

// ---------------- BFS using Adjacency List ----------------

struct Node {
int vertex;
struct Node* next;
};

struct Node* adjList[MAX];

int visitedBFS[MAX];

void addEdge(int src, int dest) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = dest;
newNode->next = adjList[src];
adjList[src] = newNode;
}

void buildAdjList() {
for (int i = 0; i < MAX; i++)
adjList[i] = NULL;

addEdge(0, 1); addEdge(0, 2); // A-B, A-C

addEdge(1, 0); addEdge(1, 3); // B-A, B-D
addEdge(2, 0); addEdge(2, 4); // C-A, C-E
addEdge(3, 1); // D-B
addEdge(4, 2); // E-C
}

void BFS(int start) {

int queue[MAX], front = 0, rear = 0;
visitedBFS[start] = 1;
queue[rear++] = start;
 while (front < rear) {
int current = queue[front++];
printf("%c ", locations[current]);

struct Node* temp = adjList[current];

while (temp) {
int v = temp->vertex;
if (!visitedBFS[v]) {
visitedBFS[v] = 1;
queue[rear++] = v;
}
temp = temp->next;
}
}
}

// ---------------- Main ----------------

int main() {
printf("DFS Traversal (Adjacency Matrix) starting from A:\n");
for (int i = 0; i < MAX; i++) visitedDFS[i] = 0;
DFS(0); // Start from A
printf("\n");

printf("\nBFS Traversal (Adjacency List) starting from A:\n");

for (int i = 0; i < MAX; i++) visitedBFS[i] = 0;
buildAdjList();
BFS(0); // Start from A
printf("\n");

return 0;
}
DFS Traversal (Adjacency Matrix) starting from A:
ABDCE

BFS Traversal (Adjacency List) starting from A:

ACBED

2. A pizza shop receives multiple orders from several locations. Assume

that one pizza boy is tasked with delivering pizzas in nearby locations,
which is represented using a graph. The time required to reach from
one location to another represents node connections. Solve the
problem of delivering a pizza to all customers in the minimum time.
Use appropriate data structures.
#include <stdio.h>
#include <limits.h>

#define MAX 100

#define INF INT_MAX

int graph[MAX][MAX]; // Adjacency matrix

int visited[MAX];
int dist[MAX];
int n; // Number of locations

// Find the vertex with minimum distance

int minDistance() {
int min = INF, min_index = -1;
for (int v = 0; v < n; v++) {
if (!visited[v] && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}

// Dijkstra's algorithm
void dijkstra(int src) {
for (int i = 0; i < n; i++) {
dist[i] = INF;
visited[i] = 0;
}
dist[src] = 0;

for (int count = 0; count < n - 1; count++) {

 int u = minDistance();
visited[u] = 1;

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

if (!visited[v] && graph[u][v] && dist[u] != INF &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}

// Print shortest delivery times

printf("\nMinimum delivery time from location %d:\n", src);
for (int i = 0; i < n; i++) {
printf("To location %d: %d minutes\n", i, dist[i]);
}
}

// Main function
int main() {
int src;
printf("Enter number of locations: ");
scanf("%d", &n);

printf("Enter time matrix (enter 0 if no direct route):\n");

for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &graph[i][j]);

printf("Enter pizza shop location (0 to %d): ", n - 1);

scanf("%d", &src);

dijkstra(src);
 return 0;
}
#output
Enter number of locations: 5
Enter time matrix:
0 10 0 30 100
10 0 50 0 0
0 50 0 20 10
30 0 20 0 60
100 0 10 60 0
Enter pizza shop location (0 to 4): 0

Minimum delivery time from location 0:

To location 0: 0 minutes
To location 1: 10 minutes
To location 2: 60 minutes
To location 3: 30 minutes
To location 4: 70 minutes

3. Implement various operations on a Binary Search Tree, such as

insertion, deletion, display, and search.

#include <stdio.h>
#include <stdlib.h>

// Define the structure of a BST node

struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}

// Insert a node into BST

struct Node* insert(struct Node* root, int value) {
if (root == NULL)
return createNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);
return root;
}

// Find the minimum value node

struct Node* findMin(struct Node* root) {
while (root->left != NULL)
root = root->left;
return root;
}

// Delete a node from BST

struct Node* delete(struct Node* root, int value) {
if (root == NULL)
return root;
if (value < root->data)
root->left = delete(root->left, value);
else if (value > root->data)
root->right = delete(root->right, value);
else {
// Node with one or no child
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;
}

// Node with two children

struct Node* temp = findMin(root->right);
root->data = temp->data;
root->right = delete(root->right, temp->data);
}
return root;
}

// Search for a value in BST

int search(struct Node* root, int value) {
if (root == NULL)
return 0;
if (value == root->data)
 return 1;
else if (value < root->data)
return search(root->left, value);
else
return search(root->right, value);
}

// In-order traversal
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

// Main function
int main() {
struct Node* root = NULL;
int choice, value;

while (1) {
printf("\n--- Binary Search Tree Operations ---\n");
printf("1. Insert\n2. Delete\n3. Search\n4. Display (In-order)\n5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
root = insert(root, value);
break;
 case 2:
printf("Enter value to delete: ");
scanf("%d", &value);
root = delete(root, value);
break;
case 3:
printf("Enter value to search: ");
scanf("%d", &value);
if (search(root, value))
printf("Value found in BST.\n");
else
printf("Value not found.\n");
break;
case 4:
printf("BST in-order traversal: ");
inorder(root);
printf("\n");
break;
case 5:
printf("Exiting...\n");
exit(0);
default:
printf("Invalid choice. Try again.\n");
}
}

return 0;
}

## output
--- Binary Search Tree Operations ---
1. Insert
2. Delete
3. Search
4. Display (In-order)
5. Exit
Enter your choice: 1
Enter value to insert: 50

Enter your choice: 1

Enter value to insert: 30

Enter your choice: 4

BST in-order traversal: 30 50

4. Construct an expression tree from the given prefix expression, e.g., +--
a*bc/def, traverse it using post-order traversal (non-recursive), and
then delete the entire tree.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 100

// Tree node structure

typedef struct Node {
char data;
struct Node* left;
struct Node* right;
} Node;

// Stack for tree nodes

typedef struct {
Node* items[MAX];
int top;
} Stack;

void initStack(Stack* s) {
s->top = -1;
}

int isEmpty(Stack* s) {
return s->top == -1;
}

void push(Stack* s, Node* node) {

s->items[++s->top] = node;
}

Node* pop(Stack* s) {
return s->items[s->top--];
}

// Create a new tree node

Node* createNode(char data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
 return newNode;
}

// Check if character is operator

int isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

// Build expression tree from prefix

Node* buildTree(char* expr) {
Stack s;
initStack(&s);

int len = 0;
while (expr[len] != '\0') len++;

// Traverse from right to left

for (int i = len - 1; i >= 0; i--) {
char ch = expr[i];
Node* node = createNode(ch);

if (isOperator(ch)) {
node->left = pop(&s);
node->right = pop(&s);
}
push(&s, node);
}

return pop(&s);
}

// Non-recursive post-order traversal

void postOrder(Node* root) {
 if (!root) return;

Stack s1, s2;

initStack(&s1);
initStack(&s2);

push(&s1, root);
while (!isEmpty(&s1)) {
Node* node = pop(&s1);
push(&s2, node);

if (node->left) push(&s1, node->left);

if (node->right) push(&s1, node->right);
}

while (!isEmpty(&s2)) {
Node* node = pop(&s2);
printf("%c ", node->data);
}
}

// Delete entire tree

void deleteTree(Node* root) {
if (!root) return;
deleteTree(root->left);
deleteTree(root->right);
free(root);
}

// Main function
int main() {
char expr[] = "+--a*bc/def"; // Example prefix expression
 Node* root = buildTree(expr);

printf("Post-order traversal (non-recursive): ");

postOrder(root);
printf("\n");

deleteTree(root);
printf("Expression tree deleted.\n");

return 0;
}
Post-order traversal (non-recursive): a b c * - d e f / - +
Expression tree deleted.
A list stores city names and their populations. Use a Binary Search Tree
for implementation.
Provide a facility for adding new cities, deleting a city, and updating
population values. Provide a facility to display all the city names in
ascending/descending order. Also, find how many maximum
comparisons are required to search for a particular city.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NAME 50

// BST node structure

typedef struct Node {
char city[MAX_NAME];
int population;
struct Node* left;
struct Node* right;
} Node;

// Create a new node

Node* createNode(char* city, int population) {
Node* newNode = (Node*)malloc(sizeof(Node));
strcpy(newNode->city, city);
newNode->population = population;
newNode->left = newNode->right = NULL;
return newNode;
}
// Insert a city
Node* insert(Node* root, char* city, int population) {
if (root == NULL)
return createNode(city, population);
if (strcmp(city, root->city) < 0)
root->left = insert(root->left, city, population);
else if (strcmp(city, root->city) > 0)
root->right = insert(root->right, city, population);
else
printf("City already exists.\n");
return root;
}

// Find minimum node

Node* findMin(Node* root) {
while (root->left != NULL)
root = root->left;
return root;
}

// Delete a city
Node* delete(Node* root, char* city) {
if (root == NULL) return NULL;
if (strcmp(city, root->city) < 0)
root->left = delete(root->left, city);
else if (strcmp(city, root->city) > 0)
root->right = delete(root->right, city);
else {
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
}
 else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
Node* temp = findMin(root->right);
strcpy(root->city, temp->city);
root->population = temp->population;
root->right = delete(root->right, temp->city);
}
return root;
}

// Update population
void updatePopulation(Node* root, char* city, int newPop) {
while (root != NULL) {
int cmp = strcmp(city, root->city);
if (cmp == 0) {
root->population = newPop;
printf("Population updated.\n");
return;
}
else if (cmp < 0)
root = root->left;
else
root = root->right;
}
printf("City not found.\n");
}

// Display cities in ascending order

void displayAsc(Node* root) {
if (root != NULL) {
 displayAsc(root->left);
printf("%s - Population: %d\n", root->city, root->population);
displayAsc(root->right);
}
}

// Display cities in descending order

void displayDesc(Node* root) {
if (root != NULL) {
displayDesc(root->right);
printf("%s - Population: %d\n", root->city, root->population);
displayDesc(root->left);
}
}

// Search and count comparisons

int searchComparisons(Node* root, char* city) {
int comparisons = 0;
while (root != NULL) {
comparisons++;
int cmp = strcmp(city, root->city);
if (cmp == 0)
return comparisons;
else if (cmp < 0)
root = root->left;
else
root = root->right;
}
return comparisons;
}

// Main function
int main() {
 Node* root = NULL;
int choice, population;
char city[MAX_NAME];

while (1) {
printf("\n--- City Population Manager ---\n");
printf("1. Add City\n2. Delete City\n3. Update Population\n4.
Display Ascending\n5. Display Descending\n6. Search Comparisons\n7.
Exit\n");
printf("Enter choice: ");
scanf("%d", &choice);
getchar(); // consume newline

switch (choice) {
case 1:
printf("Enter city name: ");
fgets(city, MAX_NAME, stdin);
city[strcspn(city, "\n")] = 0;
printf("Enter population: ");
scanf("%d", &population);
root = insert(root, city, population);
break;
case 2:
printf("Enter city name to delete: ");
fgets(city, MAX_NAME, stdin);
city[strcspn(city, "\n")] = 0;
root = delete(root, city);
break;
case 3:
printf("Enter city name to update: ");
fgets(city, MAX_NAME, stdin);
city[strcspn(city, "\n")] = 0;
printf("Enter new population: ");
 scanf("%d", &population);
updatePopulation(root, city, population);
break;
case 4:
printf("\nCities in Ascending Order:\n");
displayAsc(root);
break;
case 5:
printf("\nCities in Descending Order:\n");
displayDesc(root);
break;
case 6:
printf("Enter city name to search: ");
fgets(city, MAX_NAME, stdin);
city[strcspn(city, "\n")] = 0;
int comps = searchComparisons(root, city);
printf("Maximum comparisons made: %d\n", comps);
break;
case 7:
exit(0);
default:
printf("Invalid choice.\n");
}
}

return 0;
}

#output

1. Add City → Pune, 7000000

1. Add City → Mumbai, 12000000
4. Display Ascending
 → Mumbai - 12000000
→ Pune - 7000000
6. Search Comparisons → Pune→ Maximum comparisons made: 2
Implement any application based mini project. Sample mini projects can be
selected from the list given here [not limited to]
• Implementation of Snake and Ladder [BFS]
• Implementation of Maze generation [DFS]
• Implementation of Flight Reservation System [Searching and
Sorting]
• Implementation of Student Database Management system
[Hashing]
• Implementation of Job Scheduling [Graphs]
• Implementation of Palindrome checker [Stacks and Queues]
• Implementation of Queue using Two Stacks
• Implementation of Keyword Frequency Counter [Hash Table]
• Implementation of a basic version of a web browser’s back button
functionality [Stack]