IMPLEMENTATION OF RECURSIVE FUNCTION FOR TREE TRAVERSAL AND

FIBONACCI - c program

#include <stdio.h>

#include <stdlib.h>

struct Node {

int data;

struct Node *left, *right;

};

// Creating 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;

// Inorder Traversal (Left, Root, Right)

void inorder(struct Node* root) {

if (root == NULL)

return;

inorder(root->left);

printf("%d ", root->data);

inorder(root->right);

}
// Preorder Traversal (Root, Left, Right)

void preorder(struct Node* root) {

if (root == NULL)

return;

printf("%d ", root->data);

preorder(root->left);

preorder(root->right);

// Postorder Traversal (Left, Right, Root)

void postorder(struct Node* root) {

if (root == NULL)

return;

postorder(root->left);

postorder(root->right);

printf("%d ", root->data);

int main() {

// Creating a simple tree

/*

/\
 2 3

/\

4 5

*/

struct Node* root = createNode(1);

root->left = createNode(2);

root->right = createNode(3);

root->left->left = createNode(4);

root->left->right = createNode(5);

printf("Inorder Traversal: ");

inorder(root);

printf("\nPreorder Traversal: ");

preorder(root);

printf("\nPostorder Traversal: ");

postorder(root);

return 0;

#include <stdio.h>
// Recursive Fibonacci function

int fibonacci(int n) {

if (n <= 1)

return n;

return fibonacci(n - 1) + fibonacci(n - 2);

int main() {

int n;

printf("Enter the number of terms: ");

scanf("%d", &n);

printf("Fibonacci Series: ");

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

printf("%d ", fibonacci(i));

return 0;

}
IMPLEMENTATION OF ITERATIVE FUNCTION FOR TREE
TRAVERSAL AND FIBONACCI

#include <stdio.h>

#include <stdlib.h>

struct Node {

int data;

struct Node *left, *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;

// ------------------ ITERATIVE INORDER ------------------

void inorderIterative(struct Node* root) {

struct Node* stack[100];

int top = -1;

struct Node* current = root;

while (current != NULL || top != -1) {

 while (current != NULL) {

stack[++top] = current;

current = current->left;

current = stack[top--];

printf("%d ", current->data);

current = current->right;

// ------------------ ITERATIVE PREORDER ------------------

void preorderIterative(struct Node* root) {

if (root == NULL) return;

struct Node* stack[100];

int top = -1;

stack[++top] = root;

while (top != -1) {

struct Node* node = stack[top--];

printf("%d ", node->data);

if (node->right)
 stack[++top] = node->right;

if (node->left)

stack[++top] = node->left;

// ------------------ ITERATIVE POSTORDER ------------------

void postorderIterative(struct Node* root) {

if (root == NULL) return;

struct Node *stack1[100], *stack2[100];

int top1 = -1, top2 = -1;

stack1[++top1] = root;

while (top1 != -1) {

struct Node* node = stack1[top1--];

stack2[++top2] = node;

if (node->left)

stack1[++top1] = node->left;

if (node->right)

stack1[++top1] = node->right;

}
 while (top2 != -1) {

printf("%d ", stack2[top2--]->data);

int main() {

// Tree:

/*

/\

2 3

/\

4 5

*/

struct Node* root = createNode(1);

root->left = createNode(2);

root->right = createNode(3);

root->left->left = createNode(4);

root->left->right = createNode(5);

printf("Iterative Inorder Traversal: ");

inorderIterative(root);

printf("\nIterative Preorder Traversal: ");

 preorderIterative(root);

printf("\nIterative Postorder Traversal: ");

postorderIterative(root);

return 0;

#include <stdio.h>

int main() {

int n;

printf("Enter number of terms: ");

scanf("%d", &n);

int a = 0, b = 1, c;

printf("Fibonacci Series: ");

if (n >= 1) printf("%d ", a);

if (n >= 2) printf("%d ", b);

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

c = a + b;

printf("%d ", c);

 a = b;

b = c;

return 0;

IMPLEMENTATION OF MERGE SORT

#include <stdio.h>

// Function to merge two halves

void merge(int arr[], int left, int mid, int right) {

int i = left;

int j = mid + 1;

int k = 0;

int temp[right - left + 1];

// Merging two sorted halves

while (i <= mid && j <= right) {

if (arr[i] <= arr[j])

temp[k++] = arr[i++];

else

temp[k++] = arr[j++];

// Copy remaining elements of left half

while (i <= mid)

temp[k++] = arr[i++];

// Copy remaining elements of right half

while (j <= right)

 temp[k++] = arr[j++];

// Copy sorted temp array into original array

for (i = left, k = 0; i <= right; i++, k++)

arr[i] = temp[k];

IMPLEMENTATION OF QUICK SORT

#include <stdio.h>

// Function to swap

void swap(int *a, int *b) {

int temp = *a;

*a = *b;

*b = temp;

// Partition function

int partition(int arr[], int low, int high) {

int pivot = arr[high]; // choose last element as pivot

int i = low - 1;

for (int j = low; j < high; j++) {

if (arr[j] < pivot) {

 i++;

swap(&arr[i], &arr[j]);

// Place pivot in correct position

swap(&arr[i + 1], &arr[high]);

return i + 1;

// Quick Sort function

void quickSort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high); // Partition index

quickSort(arr, low, pi - 1); // Sort left side

quickSort(arr, pi + 1, high); // Sort right side

int main() {

int n;

printf("Enter number of elements: ");

scanf("%d", &n);
 int arr[n];

printf("Enter %d elements:\n", n);

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

scanf("%d", &arr[i]);

quickSort(arr, 0, n - 1);

printf("Sorted array: ");

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

printf("%d ", arr[i]);

return 0;

Implemetation of Binary Search tree

#include <stdio.h>

#include <stdlib.h>

// Structure of a BST node

struct Node {

int data;

struct Node *left, *right;

};

// Function to 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;

// Function to 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;

// Function to search a value in BST

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);

// Inorder traversal of BST (sorted order)

void inorder(struct Node* root) {

if (root != NULL) {

inorder(root->left);

printf("%d ", root->data);

inorder(root->right);

int main() {

struct Node* root = NULL;

int n, value, key;

printf("Enter number of nodes: ");

scanf("%d", &n);

printf("Enter %d values:\n", n);

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

scanf("%d", &value);
 root = insert(root, value);

printf("\nInorder Traversal of BST: ");

inorder(root);

printf("\n\nEnter value to search: ");

scanf("%d", &key);

if (search(root, key) != NULL)

printf("Element %d found in the BST\n", key);

else

printf("Element %d not found in the BST\n", key);

return 0;

HEAP IMPLEMENTATION

#include <stdio.h>

#define MAX 100

int heap[MAX];

int size = 0;
// Function to insert an element into the max heap

void insert(int value) {

if (size >= MAX) {

printf("Heap is full!\n");

return;

size++;

heap[size] = value;

int i = size;

int parent = i / 2;

// Heapify Up

while (i > 1 && heap[parent] < heap[i]) {

int temp = heap[parent];

heap[parent] = heap[i];

heap[i] = temp;

i = parent;

parent = i / 2;

printf("Inserted %d\n", value);

}
// Function to delete the root (max element)

int deleteMax() {

if (size == 0) {

printf("Heap is empty!\n");

return -1;

int max = heap[1];

heap[1] = heap[size];

size--;

int i = 1;

// Heapify Down

while (1) {

int left = i * 2;

int right = i * 2 + 1;

int largest = i;

if (left <= size && heap[left] > heap[largest])

largest = left;

if (right <= size && heap[right] > heap[largest])

largest = right;
 if (largest != i) {

int temp = heap[i];

heap[i] = heap[largest];

heap[largest] = temp;

i = largest;

} else {

break;

return max;

// Function to display the heap

void display() {

if (size == 0) {

printf("Heap is empty!\n");

return;

printf("Heap elements: ");

for (int i = 1; i <= size; i++) {

printf("%d ", heap[i]);

}
 printf("\n");

int main() {

int choice, value;

while (1) {

printf("\n--- MAX HEAP OPERATIONS ---\n");

printf("1. Insert\n");

printf("2. Delete Max\n");

printf("3. Display\n");

printf("4. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter value: ");

scanf("%d", &value);

insert(value);

break;

case 2:

value = deleteMax();

if (value != -1)
 printf("Deleted max value: %d\n", value);

break;

case 3:

display();

break;

case 4:

return 0;

default:

printf("Invalid choice!\n");

FIBBONACI HEAP IMPLEMENTATION

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

typedef struct Node {

int key;

int degree;

struct Node *parent;

 struct Node *child;

struct Node *left;

struct Node *right;

int mark;

} Node;

typedef struct FibonacciHeap {

Node *min;

int n;

} FibonacciHeap;

// Create a new node

Node* createNode(int key) {

Node* node = (Node*) malloc(sizeof(Node));

node->key = key;

node->degree = 0;

node->parent = node->child = NULL;

node->left = node->right = node;

node->mark = 0;

return node;

// Create an empty heap

FibonacciHeap* createHeap() {

FibonacciHeap* H = (FibonacciHeap*) malloc(sizeof(FibonacciHeap));

 H->min = NULL;

H->n = 0;

return H;

// Insert node into root list

void insert(FibonacciHeap* H, int key) {

Node* x = createNode(key);

if (H->min == NULL) {

H->min = x;

} else {

x->left = H->min;

x->right = H->min->right;

H->min->right->left = x;

H->min->right = x;

if (x->key < H->min->key)

H->min = x;

H->n++;

printf("Inserted %d\n", key);

// Merge root lists

FibonacciHeap* heapUnion(FibonacciHeap* H1, FibonacciHeap* H2) {

FibonacciHeap* H = createHeap();

H->min = H1->min;

if (H1->min != NULL && H2->min != NULL) {

Node* temp = H1->min->right;

H1->min->right = H2->min->right;

H2->min->right->left = H1->min;

H2->min->right = temp;

temp->left = H2->min;

if (H2->min->key < H1->min->key)

H->min = H2->min;

} else if (H1->min == NULL) {

H->min = H2->min;

H->n = H1->n + H2->n;

return H;

// Link two trees of equal degree

void heapLink(FibonacciHeap* H, Node* y, Node* x) {

y->left->right = y->right;
 y->right->left = y->left;

y->parent = x;

if (x->child == NULL) {

x->child = y;

y->left = y->right = y;

} else {

y->left = x->child;

y->right = x->child->right;

x->child->right->left = y;

x->child->right = y;

x->degree++;

y->mark = 0;

// Consolidate heap after extract-min

void consolidate(FibonacciHeap* H) {

int maxDegree = 45;

Node* A[50] = { NULL };

Node* w = H->min;

if (w == NULL) return;
Node* start = w;

do {

Node* x = w;

int d = x->degree;

while (A[d] != NULL) {

Node* y = A[d];

if (x->key > y->key) {

Node* temp = x; x = y; y = temp;

heapLink(H, y, x);

A[d] = NULL;

d++;

A[d] = x;

w = w->right;

} while (w != start);

H->min = NULL;

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

if (A[i] != NULL) {

if (H->min == NULL) {

H->min = A[i];

A[i]->left = A[i]->right = A[i];

 } else {

A[i]->left = H->min;

A[i]->right = H->min->right;

H->min->right->left = A[i];

H->min->right = A[i];

if (A[i]->key < H->min->key)

H->min = A[i];

// Extract minimum node

int extractMin(FibonacciHeap* H) {

Node* z = H->min;

if (z == NULL) {

printf("Heap empty!\n");

return -1;

if (z->child != NULL) {

Node* x = z->child;

do {

x->parent = NULL;
 x = x->right;

} while (x != z->child);

if (z->right == z) {

H->min = NULL;

} else {

z->left->right = z->right;

z->right->left = z->left;

H->min = z->right;

H->n--;

consolidate(H);

int minKey = z->key;

free(z);

return minKey;

int main() {

FibonacciHeap* H = createHeap();

int choice, value;

while (1) {

printf("\n--- FIBONACCI HEAP OPERATIONS ---\n");

printf("1. Insert\n");

printf("2. Extract Min\n");

printf("3. Find Min\n");

printf("4. Exit\n");

printf("Enter choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter value: ");

scanf("%d", &value);

insert(H, value);

break;

case 2:

value = extractMin(H);

if (value != -1)

printf("Extracted Min: %d\n", value);

break;

case 3:

if (H->min)

printf("Min = %d\n", H->min->key);

 else

printf("Heap empty!\n");

break;

case 4:

return 0;

default:

printf("Invalid choice!\n");

GRAPH TRAVERSAL – BREADTH FIRST SEARCH (BFS) – C PROGRAM

#include <stdio.h>

#define MAX 20

int queue[MAX];

int front = 0, rear = -1;

// Enqueue

void enqueue(int v) {
 queue[++rear] = v;

// Dequeue

int dequeue() {

return queue[front++];

// BFS function

void BFS(int adj[][MAX], int visited[], int n, int start) {

int i;

// Mark start node visited and enqueue it

visited[start] = 1;

enqueue(start);

printf("BFS Traversal: ");

while (front <= rear) {

int node = dequeue();

printf("%d ", node);

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

if (adj[node][i] == 1 && visited[i] == 0) {

visited[i] = 1;
 enqueue(i);

int main() {

int n, adj[MAX][MAX], visited[MAX] = {0};

int start, i, j;

printf("Enter number of vertices: ");

scanf("%d", &n);

printf("Enter adjacency matrix:\n");

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

for (j = 0; j < n; j++) {

scanf("%d", &adj[i][j]);

printf("Enter starting vertex: ");

scanf("%d", &start);

BFS(adj, visited, n, start);

 return 0;

DEPTH FIRST SEARCH (DFS) – C PROGRAM

#include <stdio.h>

#define MAX 20

void DFS(int adj[][MAX], int visited[], int n, int start) {

int i;

// Mark the current node as visited

visited[start] = 1;

printf("%d ", start);

// Visit all adjacent unvisited nodes

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

if (adj[start][i] == 1 && visited[i] == 0) {

DFS(adj, visited, n, i);

int main() {
 int n, adj[MAX][MAX], visited[MAX] = {0};

int start, i, j;

printf("Enter number of vertices: ");

scanf("%d", &n);

printf("Enter adjacency matrix:\n");

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

for (j = 0; j < n; j++) {

scanf("%d", &adj[i][j]);

printf("Enter starting vertex: ");

scanf("%d", &start);

printf("DFS Traversal: ");

DFS(adj, visited, n, start);

return 0;

SPANNING TREE IMPLEMENTATION -PRIM’S ALGORITHM

#include <stdio.h>
#define INF 999

#define MAX 20

int main() {

int n, i, j;

int adj[MAX][MAX];

int selected[MAX] = {0};

int edges = 0;

int x, y; // edge indices

printf("Enter number of vertices: ");

scanf("%d", &n);

printf("Enter adjacency matrix (enter 0 for no edge):\n");

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

for (j = 0; j < n; j++) {

scanf("%d", &adj[i][j]);

if (adj[i][j] == 0 && i != j)

adj[i][j] = INF; // no edge

selected[0] = 1; // start with vertex 0

 printf("\nEdges in Minimum Spanning Tree:\n");

while (edges < n - 1) {

int min = INF;

x = y = 0;

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

if (selected[i]) {

for (j = 0; j < n; j++) {

if (!selected[j] && adj[i][j] < min) {

min = adj[i][j];

x = i;

y = j;

printf("%d - %d : %d\n", x, y, min);

selected[y] = 1;

edges++;

return 0;

}
SPANNING TREE IMPLEMENTATION -KRUSKAL’S ALGORITHM

#include <stdio.h>

#define MAX 20

int parent[MAX];

// Find root of a set

int find(int i) {

while (parent[i] != i)

i = parent[i];

return i;

// Union two sets

void union_set(int i, int j) {

int a = find(i);

int b = find(j);

parent[a] = b;

int main() {

int n, i, j;
int cost[MAX][MAX];

int min, a, b, u, v, edges = 1;

printf("Enter number of vertices: ");

scanf("%d", &n);

printf("Enter cost adjacency matrix (0 for no edge):\n");

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

for (j = 0; j < n; j++) {

scanf("%d", &cost[i][j]);

if (cost[i][j] == 0)

cost[i][j] = 999; // infinity

// Make each vertex a separate set

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

parent[i] = i;

printf("\nEdges in Minimum Spanning Tree:\n");

while (edges < n) {

min = 999;

// Find minimum cost edge

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

for (j = 0; j < n; j++) {

if (cost[i][j] < min) {

min = cost[i][j];

a = u = i;

b = v = j;

u = find(u);

v = find(v);

// If including this edge doesn't cause cycle

if (u != v) {

printf("%d - %d : %d\n", a, b, min);

union_set(u, v);

edges++;

// Remove this edge from graph

cost[a][b] = cost[b][a] = 999;

return 0;
}

SHORTEST PATH ALGORITHMS-DIJKSTRA'S ALGORITHM

#include <stdio.h>

#define MAX 20

#define INF 9999

int main() {

int n, i, j, start;

int cost[MAX][MAX], dist[MAX], visited[MAX] = {0};

printf("Enter number of vertices: ");

scanf("%d", &n);

printf("Enter adjacency matrix (0 for no edge):\n");

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

for (j = 0; j < n; j++) {

scanf("%d", &cost[i][j]);

if (cost[i][j] == 0 && i != j)

cost[i][j] = INF;

}
printf("Enter starting vertex: ");

scanf("%d", &start);

// Initialize distances

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

dist[i] = cost[start][i];

visited[start] = 1;

dist[start] = 0;

// Dijkstra’s algorithm

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

int min = INF, u = -1;

// Pick the unvisited vertex with the smallest distance

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

if (!visited[i] && dist[i] < min) {

min = dist[i];

u = i;

visited[u] = 1;

// Update distances
 for (j = 0; j < n; j++) {

if (!visited[j] && dist[u] + cost[u][j] < dist[j])

dist[j] = dist[u] + cost[u][j];

// Output shortest distances

printf("\nShortest distances from vertex %d:\n", start);

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

printf("%d → %d = %d\n", start, i, dist[i]);

return 0;

SHORTEST PATH ALGORITHMS-BELLMANN FORD ALGORITHM

#include <stdio.h>

#include <stdlib.h>

#define MAX 20

#define INF 9999

typedef struct {

int u, v, w; // edge from u to v with weight w

} Edge;
int main() {

int n, e, i, j, start;

Edge edges[MAX];

printf("Enter number of vertices: ");

scanf("%d", &n);

printf("Enter number of edges: ");

scanf("%d", &e);

printf("Enter edges (u v w):\n");

for (i = 0; i < e; i++) {

scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);

printf("Enter starting vertex: ");

scanf("%d", &start);

int dist[MAX];

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

dist[i] = INF;

dist[start] = 0;

// Relax all edges n-1 times

for (i = 1; i <= n - 1; i++) {

 for (j = 0; j < e; j++) {

int u = edges[j].u;

int v = edges[j].v;

int w = edges[j].w;

if (dist[u] != INF && dist[u] + w < dist[v])

dist[v] = dist[u] + w;

// Check for negative-weight cycles

for (i = 0; i < e; i++) {

int u = edges[i].u;

int v = edges[i].v;

int w = edges[i].w;

if (dist[u] != INF && dist[u] + w < dist[v]) {

printf("Graph contains negative weight cycle\n");

return 0;

// Print shortest distances

printf("\nShortest distances from vertex %d:\n", start);

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

 printf("%d → %d = %d\n", start, i, dist[i]);

return 0;

IMPLEMENTATION OF MATRIX CHAIN MULTIPLICATION

#include <stdio.h>

#include <limits.h>

int min(int a, int b) {

return (a < b) ? a : b;

int matrixChainMultiplication(int p[], int n) {

int m[n][n]; // m[i][j] stores minimum multiplications

// cost is zero when multiplying one matrix

for (int i = 1; i < n; i++)

m[i][i] = 0;

// L is chain length

for (int L = 2; L < n; L++) {

for (int i = 1; i <= n - L; i++) {

int j = i + L - 1;
 m[i][j] = INT_MAX;

for (int k = i; k < j; k++) {

int q = m[i][k] + m[k + 1][j] + p[i - 1]*p[k]*p[j];

if (q < m[i][j])

m[i][j] = q;

return m[1][n - 1];

int main() {

int n;

printf("Enter number of matrices: ");

scanf("%d", &n);

int p[n+1];

printf("Enter dimensions (p0 p1 ... pn):\n");

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

scanf("%d", &p[i]);

int minCost = matrixChainMultiplication(p, n + 1);

 printf("Minimum number of multiplications = %d\n", minCost);

return 0;

Implementation of activity selection

#include <stdio.h>

typedef struct {

int start;

int finish;

} Activity;

// Function to sort activities by finish time

void sortByFinish(Activity arr[], int n) {

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

for (int j = i + 1; j < n; j++) {

if (arr[i].finish > arr[j].finish) {

Activity temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}
 }

void activitySelection(Activity arr[], int n) {

sortByFinish(arr, n);

printf("Selected activities:\n");

int i = 0;

printf("%d ", i);

for (int j = 1; j < n; j++) {

if (arr[j].start >= arr[i].finish) {

printf("%d ", j);

i = j;

int main() {

int n;

printf("Enter number of activities: ");

scanf("%d", &n);
 Activity arr[n];

printf("Enter start and finish times:\n");

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

scanf("%d %d", &arr[i].start, &arr[i].finish);

activitySelection(arr, n);

return 0;

IMPLEMENTATION OF HUFFMAN CODING

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX 100

// Node structure

typedef struct Node {

char data;

unsigned freq;

struct Node *left, *right;

} Node;
// Min Heap structure

typedef struct MinHeap {

unsigned size;

unsigned capacity;

Node **array;

} MinHeap;

// Create a new node

Node* newNode(char data, unsigned freq) {

Node* temp = (Node*)malloc(sizeof(Node));

temp->data = data;

temp->freq = freq;

temp->left = temp->right = NULL;

return temp;

// Create min heap of given capacity

MinHeap* createMinHeap(unsigned capacity) {

MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));

minHeap->size = 0;

minHeap->capacity = capacity;

minHeap->array = (Node**)malloc(minHeap->capacity * sizeof(Node*));

return minHeap;

}
// Swap two nodes

void swapNode(Node** a, Node** b) {

Node* t = *a;

*a = *b;

*b = t;

// Heapify at given index

void minHeapify(MinHeap* minHeap, int idx) {

int smallest = idx;

int left = 2*idx + 1;

int right = 2*idx + 2;

if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)

smallest = left;

if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]-

>freq)

smallest = right;

if (smallest != idx) {

swapNode(&minHeap->array[smallest], &minHeap->array[idx]);

minHeapify(minHeap, smallest);

}
// Check if size is 1

int isSizeOne(MinHeap* minHeap) {

return (minHeap->size == 1);

// Extract min

Node* extractMin(MinHeap* minHeap) {

Node* temp = minHeap->array[0];

minHeap->array[0] = minHeap->array[minHeap->size - 1];

minHeap->size--;

minHeapify(minHeap, 0);

return temp;

// Insert a node into min heap

void insertMinHeap(MinHeap* minHeap, Node* node) {

minHeap->size++;

int i = minHeap->size - 1;

while (i && node->freq < minHeap->array[(i - 1)/2]->freq) {

minHeap->array[i] = minHeap->array[(i - 1)/2];

i = (i - 1)/2;

minHeap->array[i] = node;
}

// Build min heap

void buildMinHeap(MinHeap* minHeap) {

int n = minHeap->size - 1;

for (int i = (n - 1)/2; i >= 0; i--)

minHeapify(minHeap, i);

// Create and build min heap from characters and frequencies

MinHeap* createAndBuildMinHeap(char data[], int freq[], int n) {

MinHeap* minHeap = createMinHeap(n);

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

minHeap->array[i] = newNode(data[i], freq[i]);

minHeap->size = n;

buildMinHeap(minHeap);

return minHeap;

// Build Huffman Tree

Node* buildHuffmanTree(char data[], int freq[], int n) {

Node *left, *right, *top;

MinHeap* minHeap = createAndBuildMinHeap(data, freq, n);

 while (!isSizeOne(minHeap)) {

left = extractMin(minHeap);

right = extractMin(minHeap);

top = newNode('$', left->freq + right->freq);

top->left = left;

top->right = right;

insertMinHeap(minHeap, top);

return extractMin(minHeap);

// Print Huffman codes from the root

void printCodes(Node* root, int arr[], int top) {

if (root->left) {

arr[top] = 0;

printCodes(root->left, arr, top + 1);

if (root->right) {

arr[top] = 1;

printCodes(root->right, arr, top + 1);

}
 if (!root->left && !root->right) {

printf("%c: ", root->data);

for (int i = 0; i < top; i++)

printf("%d", arr[i]);

printf("\n");

int main() {

int n;

printf("Enter number of characters: ");

scanf("%d", &n);

char arr[n];

int freq[n];

printf("Enter characters:\n");

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

scanf(" %c", &arr[i]);

printf("Enter their frequencies:\n");

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

scanf("%d", &freq[i]);
 Node* root = buildHuffmanTree(arr, freq, n);

int huffArr[MAX], top = 0;

printf("\nHuffman Codes:\n");

printCodes(root, huffArr, top);

return 0;