INFIX TO POSTFIX

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX 100

char stack[MAX];

int top = -1;

void push(char c) {

if (top < MAX - 1)

stack[++top] = c;}

char pop() {

if (top >= 0)

return stack[top--];

return 0;}

char peek() {

if (top >= 0)

return stack[top]; return 0;

int isOperand(char c) {

// Numbers, lowercase, or uppercase letters

return (c >= '0' && c <= '9')|

(c >= 'a' && c <= 'z')|

(c >= 'A' && c <= 'Z');

int precedence(char c) {

switch (c) {

case '+': case '-': return 1;

case '*': case '/': return 2;

case '^': return 3;

default: return 0;

void infixToPostfix(char* infix, char* postfix) {

int i=0, k=0;

char c;
 while ((c = infix[i++]) != '\0') {

if (isOperand(c)) {

postfix[k++] = c;

} else if (c == '(') {

push(c);

} else if (c == ')') {

while (top != -1 && peek() != '(')

postfix[k++] = pop();

pop(); // Remove '('

} else { // Operator

while (top != -1 && precedence(peek()) >= precedence(c))

postfix[k++] = pop();

push(c);

while (top != -1)

postfix[k++] = pop();

postfix[k] = '\0';

int main() {

char infix[MAX], postfix[MAX];

printf("Enter infix expression: ");

scanf("%s", infix);

infixToPostfix(infix, postfix);

printf("Postfix: %s\n", postfix);

return 0;

EVALUATION OF POSTFIX

#include <stdio.h>

#include <ctype.h> // for isdigit()

#define MAX 100

int stack[MAX];

int top = -1;

if (top < MAX - 1)

stack[++top] = val;

int pop() {

if (top >= 0)

return stack[top--];

return 0;

int evaluatePostfix(char* exp) {

int i;

for (i = 0; exp[i] != '\0'; i++) {

char c = exp[i];

// If character is a digit, push it to stack

if (isdigit(c)) {

push(c - '0'); // Convert char to int (e.g. '5' -> 5)

// If operator, pop top two elements and perform operation

else {

int val1 = pop();

int val2 = pop();

switch (c) {

case '+': push(val2 + val1); break;

case '-': push(val2 - val1); break;

case '*': push(val2 * val1); break;

case '/': push(val2 / val1); break;

return pop(); // Final result on stack

int main() {
 char exp[MAX];

printf("Enter Postfix Expression: ");

scanf("%s", exp);

printf("Result = %d\n", evaluatePostfix(exp));

return 0;

TREE TRAVERSAL
#include <stdio.h>

#include <stdlib.h>

// Define the structure for a tree node

struct Node {

int data;

struct Node* left;

struct Node* 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 = NULL;

newNode->right = NULL;

return newNode;

// Inorder Traversal (Left → Root → Right)

void inorderTraversal(struct Node* root) {

if (root == NULL)

return;

inorderTraversal(root->left);

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

inorderTraversal(root->right);

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

void preorderTraversal(struct Node* root) {

if (root == NULL)

return;

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

preorderTraversal(root->left);

preorderTraversal(root->right);

// Postorder Traversal (Left → Right → Root)

void postorderTraversal(struct Node* root) {

if (root == NULL)

return;

postorderTraversal(root->left);

postorderTraversal(root->right);

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

int main() {

// Create tree nodes

struct Node* root = createNode(1);

root->left = createNode(12);

root->right = createNode(9);

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

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

// Display traversals

printf("Inorder traversal: ");

inorderTraversal(root);

printf("\n");

printf("Preorder traversal: ");

preorderTraversal(root);

printf("\n");

printf("Postorder traversal: ");

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

return 0;

BST ZIG-ZAG
#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

// A structure for tree nodes

struct Node {

int data;

struct Node* left;

struct Node* 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 = NULL;

newNode->right = NULL;

return newNode;

// Function to insert a node in the 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 find the height of the tree

if (root == NULL)

return 0;

int l = height(root->left);

int r = height(root->right);

return (l > r ? l : r) + 1;

// Print nodes from left to right at a given level

void leftToRight(struct Node* root, int level) {

if (root == NULL)

return;

if (level == 1)

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

else {

leftToRight(root->left, level - 1);

leftToRight(root->right, level - 1);

// Print nodes from right to left at a given level

void rightToLeft(struct Node* root, int level) {

if (root == NULL)

return;

if (level == 1)

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

else {

rightToLeft(root->right, level - 1);

rightToLeft(root->left, level - 1);

// Function for zigzag traversal

void zigzagTraversal(struct Node* root) {

int h = height(root);

bool leftToRightDir = true;

if (leftToRightDir)

leftToRight(root, i);

else

rightToLeft(root, i);

leftToRightDir = !leftToRightDir; // Switch direction

int main() {

struct Node* root = NULL;

// Build a BST

root = insert(root, 50);

insert(root, 30);

insert(root, 70);

insert(root, 20);

insert(root, 40);

insert(root, 60);

insert(root, 80);

printf("Zigzag Level Order Traversal:\n");

zigzagTraversal(root);

printf("\n");

return 0;

LCA
#include <stdio.h>

#include <stdlib.h>

struct Node {

int data;

struct Node* left;

struct Node* right;

};
// Create a new tree node

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

newNode->left = NULL;

newNode->right = NULL;

return newNode;

// Function to find the Lowest Common Ancestor (LCA)

struct Node* findLCA(struct Node* root, int n1, int n2) {

if (root == NULL)

return NULL;

// If either n1 or n2 matches root, return root

if (root->data == n1 || root->data == n2)

return root;

// Look for nodes in left and right subtrees

struct Node* leftLCA = findLCA(root->left, n1, n2);

struct Node* rightLCA = findLCA(root->right, n1, n2);

// If both sides return non-null, current node is LCA

if (leftLCA && rightLCA)

return root;

// Otherwise, return the non-null subtree

return (leftLCA != NULL) ? leftLCA : rightLCA;

int main() {

struct Node* root = createNode(3);

root->left = createNode(5);

root->right = createNode(1);

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

root->left->right = createNode(2);
 root->right->left = createNode(0);

root->right->right = createNode(8);

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

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

int n1 = 5, n2 = 1;

struct Node* lca = findLCA(root, n1, n2);

printf("LCA of %d and %d is %d\n", n1, n2, lca->data);

n1 = 5; n2 = 4;

lca = findLCA(root, n1, n2);

printf("LCA of %d and %d is %d\n", n1, n2, lca->data);

return 0;

MIN HEAP
#include <stdio.h>

#include <stdlib.h>

#define MAX 100

struct MinHeap {

int size;

int arr[MAX];

};

// Function to swap values

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

int temp = *a;

*a = *b;

*b = temp;

// Function to heapify (maintain min heap)

void heapify(struct MinHeap *heap, int i) {

int smallest = i;

int left = 2 * i + 1;
 int right = 2 * i + 2;

if (left < heap->size && heap->arr[left] < heap->arr[smallest])

smallest = left;

if (right < heap->size && heap->arr[right] < heap->arr[smallest])

smallest = right;

if (smallest != i) {

swap(&heap->arr[i], &heap->arr[smallest]);

heapify(heap, smallest);

// Function to insert in min heap

void insert(struct MinHeap *heap, int key) {

if (heap->size == MAX) {

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

return;

int i = heap->size++;

heap->arr[i] = key;

// Fix min heap property if violated

while (i != 0 && heap->arr[(i - 1) / 2] > heap->arr[i]) {

swap(&heap->arr[i], &heap->arr[(i - 1) / 2]);

i = (i - 1) / 2;

// Extract minimum (root)

int extractMin(struct MinHeap *heap) {

if (heap->size <= 0)

return -1;

if (heap->size == 1)

return heap->arr[--heap->size];
 int root = heap->arr[0];

heap->arr[0] = heap->arr[--heap->size];

heapify(heap, 0);

return root;

// Function to print heap elements

void printHeap(struct MinHeap *heap) {

for (int i = 0; i < heap->size; i++)

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

printf("\n");

int main() {

struct MinHeap heap;

[Link] = 0;

insert(&heap, 5);

insert(&heap, 3);

insert(&heap, 8);

insert(&heap, 1);

insert(&heap, 6);

printf("Min Heap array: ");

printHeap(&heap);

printf("Extract Min: %d\n", extractMin(&heap));

printf("Heap after extraction: ");

printHeap(&heap);

return 0;

MAX HEAP
#include <stdio.h>

#include <stdlib.h>

#define MAX 100

struct MaxHeap {

int size;

int arr[MAX];

};

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

int temp = *a;

*a = *b;

*b = temp;

// Heapify to maintain Max Heap property

void heapify(struct MaxHeap *heap, int i) {

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

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

largest = left;

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

largest = right;

if (largest != i) {

swap(&heap->arr[i], &heap->arr[largest]);

heapify(heap, largest);

// Insert a new key into Max Heap

void insert(struct MaxHeap *heap, int key) {

if (heap->size == MAX) {
 printf("Heap is full!\n");

return;

int i = heap->size++;

heap->arr[i] = key;

// Fix heap property violation

while (i != 0 && heap->arr[(i - 1) / 2] < heap->arr[i]) {

swap(&heap->arr[i], &heap->arr[(i - 1) / 2]);

i = (i - 1) / 2;

// Extract maximum element (root)

int extractMax(struct MaxHeap *heap) {

if (heap->size <= 0)

return -1;

if (heap->size == 1)

return heap->arr[--heap->size];

int root = heap->arr[0];

heap->arr[0] = heap->arr[--heap->size];

heapify(heap, 0);

return root;

// Display heap as array

void printHeap(struct MaxHeap *heap) {

for (int i = 0; i < heap->size; i++)

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

printf("\n");

int main() {

struct MaxHeap heap;

[Link] = 0;
 insert(&heap, 10);

insert(&heap, 30);

insert(&heap, 20);

insert(&heap, 15);

insert(&heap, 40);

printf("Max Heap elements: ");

printHeap(&heap);

printf("Extracted Max: %d\n", extractMax(&heap));

printf("Heap after extraction: ");

printHeap(&heap);

return 0;

KTH LARGEST AND SMALLEST

#include <stdio.h>

#include <stdlib.h>

// Swap function

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

int temp = *a;

*a = *b;

*b = temp;

// Min Heapify function

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

if (right < n && arr[right] < arr[smallest])

smallest = right;

if (smallest != i) {

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

minHeapify(arr, n, smallest);

// Max Heapify function

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

// Extract root (remove top element)

int extractRoot(int arr[], int *n, int isMinHeap) {

int root = arr[0];

arr[0] = arr[--(*n)];

if (isMinHeap)

minHeapify(arr, *n, 0);

else

maxHeapify(arr, *n, 0);

return root;

}
int main() {

int arr[] = {7, 2, 9, 4, 11, 5, 3};

int n = sizeof(arr) / sizeof(arr[0]);

int k = 3;

int heap1[n], heap2[n];

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

heap1[i] = arr[i];

heap2[i] = arr[i];

// Build Min Heap for kth largest

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

minHeapify(heap1, n, i);

int size1 = n;

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

extractRoot(heap1, &size1, 1);

printf("Kth Largest Element = %d\n", heap1[0]);

// Build Max Heap for kth smallest

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

maxHeapify(heap2, n, i);

int size2 = n;

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

extractRoot(heap2, &size2, 0);

printf("Kth Smallest Element = %d\n", heap2[0]);

return 0;

OPERATIONS IN BST

#include <stdio.h>

#include <stdlib.h>

// Define the structure of a tree node

int key;

struct Node *left, *right;

};

// Create a new node

struct Node* newNode(int item) {

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

temp->key = item;

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

return temp;

// Inorder Traversal (Left, Root, Right)

void inorder(struct Node* root) {

if (root != NULL) {

inorder(root->left);

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

inorder(root->right);

// Search in BST

struct Node* search(struct Node* root, int key) {

if (root == NULL || root->key == key)

return root;

if (key < root->key)

return search(root->left, key);

return search(root->right, key);

// Insert a node

struct Node* insert(struct Node* node, int key) {

if (node == NULL)

return newNode(key);

if (key < node->key)

node->left = insert(node->left, key);

node->right = insert(node->right, key);

return node;

// Find the smallest value node (Inorder successor)

struct Node* minValueNode(struct Node* node) {

struct Node* current = node;

while (current && current->left != NULL)

current = current->left;

return current;

// Delete a node

struct Node* deleteNode(struct Node* root, int key) {

if (root == NULL)

return root;

// Traverse to find the node

if (key < root->key)

root->left = deleteNode(root->left, key);

else if (key > root->key)

root->right = deleteNode(root->right, key);

else {

// Node with only one child 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

root->key = temp->key; // Replace key with inorder successor

root->right = deleteNode(root->right, temp->key);

return root;

int main() {

struct Node* root = NULL;

root = insert(root, 8);

root = insert(root, 3);

root = insert(root, 1);

root = insert(root, 6);

root = insert(root, 7);

root = insert(root, 10);

root = insert(root, 14);

root = insert(root, 4);

printf("Inorder traversal: ");

inorder(root);

printf("\n");

printf("Deleting 10...\n");

root = deleteNode(root, 10);

printf("Inorder traversal after deletion: ");

inorder(root);

printf("\n");

int key = 7;

printf("Searching for %d: ", key);

struct Node* result = search(root, key);

if (result != NULL)

printf("Found!\n");

else

printf("Not Found!\n");

return 0;
}

DFS

#include <stdio.h>

#define MAX 10

int graph[MAX][MAX];

int visited[MAX];

int vertices;

// Function to perform DFS

void DFS(int vertex) {

printf("%d ", vertex);

visited[vertex] = 1;

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

if (graph[vertex][i] == 1 && !visited[i]) {

DFS(i);

int main() {

int edges, u, v, start;

printf("Enter number of vertices: ");

scanf("%d", &vertices);

// Initialize the adjacency matrix

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

for (int j = 0; j < vertices; j++)

graph[i][j] = 0;

printf("Enter number of edges: ");

scanf("%d", &edges);
 printf("Enter edges (u v):\n");

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

scanf("%d %d", &u, &v);

graph[u][v] = 1;

graph[v][u] = 1; // Undirected graph

printf("Enter starting vertex for DFS: ");

scanf("%d", &start);

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

visited[i] = 0;

printf("DFS Traversal: ");

DFS(start);

printf("\n");

return 0;

BFS

#include <stdio.h>

#define MAX 10

int graph[MAX][MAX];

int visited[MAX];

int queue[MAX];

int front = -1, rear = -1;

int vertices;

// BFS Implementation

void BFS(int start) {

front = 0;

rear = 0;

queue[rear] = start;
 visited[start] = 1;

printf("%d ", start);

while (front <= rear) {

int vertex = queue[front];

front++;

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

if (graph[vertex][i] == 1 && !visited[i]) {

queue[++rear] = i;

visited[i] = 1;

printf("%d ", i);

int main() {

int edges, u, v, start;

printf("Enter number of vertices: ");

scanf("%d", &vertices);

// Initialize adjacency matrix

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

for (int j = 0; j < vertices; j++)

graph[i][j] = 0;

printf("Enter number of edges: ");

scanf("%d", &edges);

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

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

scanf("%d %d", &u, &v);

graph[u][v] = 1;

graph[v][u] = 1; // Undirected graph

printf("Enter starting vertex for BFS: ");

scanf("%d", &start);

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

visited[i] = 0;

printf("BFS Traversal: ");

BFS(start);

printf("\n");

return 0;

PRIMS

#include <stdio.h>

#include <limits.h>

#include <stdbool.h>

#define V 5 // Number of vertices in the graph

// Function to find vertex with minimum weight not yet included in MST

int minWeight(int weight[], bool visited[]) {

int min = INT_MAX, min_index;

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

if (!visited[v] && weight[v] < min) {

min = weight[v];

min_index = v;

return min_index;

// Function to print the constructed MST

void printMST(int parent[], int graph[V][V]) {

printf("Edge \tWeight\n");

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

printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);

totalCost += graph[i][parent[i]];

printf("Total cost of MST: %d\n", totalCost);

// Function to construct MST using Prim's Algorithm

void primMST(int graph[V][V]) {

int parent[V]; // Stores MST

int weight[V]; // Minimum edge weights

bool visited[V]; // Visited vertices

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

weight[i] = INT_MAX;

visited[i] = false;

weight[0] = 0; // Start from vertex 0

parent[0] = -1; // Root node has no parent

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

int u = minWeight(weight, visited);

visited[u] = true;

// Update neighbors

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

if (graph[u][v] && !visited[v] && graph[u][v] < weight[v]) {

parent[v] = u;

weight[v] = graph[u][v];

// Print final MST

// Driver code

int main() {

int graph[V][V] = {

{0, 2, 0, 6, 0},

{2, 0, 3, 8, 5},

{0, 3, 0, 0, 7},

{6, 8, 0, 0, 9},

{0, 5, 7, 9, 0}

};

printf("Prim's Minimum Spanning Tree:\n");

primMST(graph);

return 0;

DIJKSTRA

#include <stdio.h>

#include <limits.h>

#include <stdbool.h>

#define V 9 // Number of vertices

// Find vertex with minimum distance value

int minDistance(int dist[], bool visited[]) {

int min = INT_MAX, min_index = -1;

for (int v = 0; v < V; v++)

if (!visited[v] && dist[v] <= min)

min = dist[v], min_index = v;

return min_index;

// Print the shortest distances

printf("Vertex \tDistance from Source\n");

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

printf("%d \t\t%d\n", i, dist[i]);

// Dijkstra’s algorithm implementation

void dijkstra(int graph[V][V], int src) {

int dist[V]; // shortest distances

bool visited[V]; // visited array

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

dist[i] = INT_MAX, visited[i] = false;

dist[src] = 0;

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

int u = minDistance(dist, visited);

visited[u] = true;

for (int v = 0; v < V; v++)

if (!visited[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v])

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

printSolution(dist);

int main() {

int graph[V][V] = {

{0, 4, 0, 0, 0, 0, 0, 8, 0},

{4, 0, 8, 0, 0, 0, 0, 11, 0},

{0, 8, 0, 7, 0, 4, 0, 0, 2},

{0, 0, 7, 0, 9, 14, 0, 0, 0},

{0, 0, 0, 9, 0, 10, 0, 0, 0},

{0, 0, 4, 14, 10, 0, 2, 0, 0},

{0, 0, 0, 0, 0, 2, 0, 1, 6},

{8, 11, 0, 0, 0, 0, 1, 0, 7},

{0, 0, 2, 0, 0, 0, 6, 7, 0}
 };

int source = 0;

printf("Dijkstra's Shortest Path (Source = %d)\n", source);

dijkstra(graph, source);

return 0;

KRUSHKAL
#include <stdio.h>

int i, j, k, a, b, u, v, n, ne = 1;

int min, mincost = 0, cost[10][10], parent[10];

// Function to find the parent of a node

int find(int i) {

while (parent[i])

i = parent[i];

return i;

// Function to merge two sets

int uni(int i, int j) {

if (i != j) {

parent[j] = i;

return 1;

return 0;

int main() {

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

scanf("%d", &n);

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

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

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

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

cost[i][j] = 999; // Treat 0 as infinity

printf("\nThe edges of Minimum Cost Spanning Tree are:\n");

while (ne < n) {

for (i = 1, min = 999; i <= n; i++) {

for (j = 1; 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 (uni(u, v)) {

printf("%d edge (%d,%d) = %d\n", ne++, a, b, min);

mincost += min;

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

printf("\nMinimum cost = %d\n", mincost);

return 0;