DSA Unit 3
/notesGraphs and Trees
Binary Search Tree (BST)
Using Linked List (Malloc)
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;
}
struct Node* insert(struct Node* root, int value) {
if (root == NULL) {
return createNode(value);
}
if (value > root->data) {
root->right = insert(root->right, value);
}
else if (value < root->data) {
root->left = insert(root->left, value);
}
return root;
}
// Deletion
struct Node* findMin(struct Node* node) {
struct Node* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
struct Node* deleteNode(struct Node* root, int value) {
if (root == NULL) return root;
if (value < root->data) {
root->left = deleteNode(root->left, value);
}
else if (value > root->data) {
root->right = deleteNode(root->right, value);
}
else {
// Case 1 & 2: 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;
}
// Case 3: Two Children
struct Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}BST Using Array
In Zero-Based Indexing (Root at 0): For parent node at i, left child at 2i + 1 and right child at 2i + 2. Parent of node at i is [(i-1)/2].
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 20
int tree[MAX_SIZE];
void initTree() {
for (int i = 0; i < MAX_SIZE; i++) {
tree[i] = 0;
}
}
void insert(int value) {
int currentIndex = 0;
while (currentIndex < MAX_SIZE) {
if (tree[currentIndex] == 0) {
tree[currentIndex] = value;
printf("Inserted %d at index %d\n", value, currentIndex);
return;
}
if (value < tree[currentIndex]) {
currentIndex = 2 * currentIndex + 1;
} else {
currentIndex = 2 * currentIndex + 2;
}
}
printf("Error: Tree is full, cannot insert %d\n", value);
}
void inorder(int index) {
if (index >= MAX_SIZE || tree[index] == 0) {
return;
}
inorder(2 * index + 1);
printf("%d ", tree[index]);
inorder(2 * index + 2);
}Binary Expression Trees
Binary expression trees represent mathematical expressions where operands are leaves and operators are internal nodes. We can construct them from postfix expressions.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node {
char data;
struct Node *left, *right;
};
#define MAX_STACK_SIZE 100
struct Node* stack[MAX_STACK_SIZE];
int top = -1;
void push(struct Node* node) {
if (top < MAX_STACK_SIZE - 1) {
stack[++top] = node;
}
}
struct Node* pop() {
if (top >= 0) {
return stack[top--];
}
return NULL;
}
struct Node* newNode(char val) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
int isOperand(char c) {
return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
}
struct Node* buildExpressionTree(char* postfix) {
int i = 0;
while (postfix[i] != '\0') {
char symbol = postfix[i];
if (isOperand(symbol)) {
push(newNode(symbol));
} else {
struct Node* operatorNode = newNode(symbol);
operatorNode->right = pop();
operatorNode->left = pop();
push(operatorNode);
}
i++;
}
return pop();
}
void inorder(struct Node* root) {
if (root) {
if (!isOperand(root->data)) printf("(");
inorder(root->left);
printf("%c", root->data);
inorder(root->right);
if (!isOperand(root->data)) printf(")");
}
}Threaded Binary Trees
Full Threaded Binary Tree (Inorder)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
int lthread;
int rthread;
};
struct Node* leftmost(struct Node* node) {
if (node == NULL) return NULL;
while (node->lthread == 0) {
node = node->left;
}
return node;
}
struct Node* InorderSuccessor(struct Node* ptr) {
if (ptr->rthread == 1) {
return ptr->right;
}
ptr = ptr->right;
while (ptr != NULL && ptr->lthread == 0) {
ptr = ptr->left;
}
return ptr;
}
void inorderTraversal(struct Node* root) {
if (root == NULL) {
printf("Tree is empty.\n");
return;
}
struct Node* ptr = leftmost(root);
while (ptr != NULL) {
printf("%d ", ptr->data);
ptr = InorderSuccessor(ptr);
}
printf("\n");
}Right Threaded Binary Tree (Inorder)
struct Node {
int data;
struct Node *left;
struct Node *right;
int rthread;
};
struct Node* leftmost(struct Node* node) {
if (node == NULL) return NULL;
while (node->left != NULL) {
node = node->left;
}
return node;
}
struct Node* InorderSuccessor(struct Node* ptr) {
if (ptr->rthread == 1) {
return ptr->right;
}
ptr = ptr->right;
while (ptr != NULL && ptr->left != NULL) {
ptr = ptr->left;
}
return ptr;
}
void inorderTraversal(struct Node* root) {
if (root == NULL) {
printf("Tree is empty.\n");
return;
}
struct Node* ptr = leftmost(root);
while (ptr != NULL) {
printf("%d ", ptr->data);
ptr = InorderSuccessor(ptr);
}
printf("\n");
}Heaps
Heaps are special binary trees with two key properties:
- Structural Property: Must be a complete binary tree (except last level may not be full)
- Heap Property: Parent value should be greater than (max heap) or less than (min heap) both children
- No rule that left > right
- If there are n nodes, height is ⌊log₂n⌋
- First n/2 elements are parents, last n/2 are children
Max Heap - Bottom-Up Heapification
#include <stdio.h>
#include <stdlib.h>
void heapBottomUp(int H[], int n) {
for (int i = n / 2; i >= 1; i--) {
int k = i;
int v = H[k];
int heap = 0;
while (heap == 0 && 2 * k <= n) {
int j = 2 * k;
if (j < n) {
if (H[j] < H[j + 1]) {
j = j + 1;
}
}
if (v >= H[j]) {
heap = 1;
} else {
H[k] = H[j];
k = j;
}
}
H[k] = v;
}
}
int main() {
int arr[10] = {0, 4, 1, 3, 2, 16, 9, 10, 14, 8};
int N = 9;
printf("Original array (1-indexed): ");
for (int i = 1; i <= N; i++) {
printf("%d ", arr[i]);
}
printf("\n");
heapBottomUp(arr, N);
printf("Max Heap array (1-indexed): ");
for (int i = 1; i <= N; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Max Heap - Top-Down Approach + Heap Sort
#include <stdio.h>
#define MAX 50
int main() {
int a[MAX];
int i, c, p, n, elt;
printf("Enter the number of elements (max %d):\n", MAX);
if (scanf("%d", &n) != 1 || n <= 0 || n > MAX) {
printf("Invalid number of elements.\n");
return 1;
}
printf("Enter the elements:\n");
for (i = 0; i < n; i++) {
if (scanf("%d", &a[i]) != 1) {
printf("Error reading element.\n");
return 1;
}
}
// HEAPIFY: BUILD MAX HEAP (Top-Down / Sift-Up)
for (i = 1; i < n; i++) {
elt = a[i];
c = i;
p = (c - 1) / 2;
while (c > 0 && a[p] < elt) {
a[c] = a[p];
c = p;
p = (c - 1) / 2;
}
a[c] = elt;
}
printf("\nElements of Max Heap:\n");
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
// HEAP SORT
for (i = n - 1; i > 0; i--) {
elt = a[i];
a[i] = a[0];
a[0] = elt;
elt = a[0];
p = 0;
while (2 * p + 1 < i) {
c = 2 * p + 1;
if (c + 1 < i && a[c] < a[c + 1]) {
c = c + 1;
}
if (elt >= a[c]) {
break;
}
a[p] = a[c];
p = c;
}
a[p] = elt;
}
printf("\nSorted elements (Heap sort):\n");
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}Min Heap - Bottom-Up
void heapBottomUpMin(int H[], int n) {
for (int i = n / 2; i >= 1; i--) {
int k = i;
int v = H[k];
int heap = 0;
while (heap == 0 && 2 * k <= n) {
int j = 2 * k;
if (j < n) {
if (H[j] > H[j + 1]) {
j = j + 1;
}
}
if (v <= H[j]) {
heap = 1;
} else {
H[k] = H[j];
k = j;
}
}
H[k] = v;
}
}Min Heap - Top-Down
// HEAPIFY: BUILD MIN HEAP (Top-Down / Sift-Up)
for (i = 1; i < n; i++) {
elt = a[i];
c = i;
p = (c - 1) / 2;
while (c > 0 && a[p] > elt) {
a[c] = a[p];
c = p;
p = (c - 1) / 2;
}
a[c] = elt;
}
// MIN HEAP SORT
for (i = n - 1; i > 0; i--) {
elt = a[i];
a[i] = a[0];
a[0] = elt;
elt = a[0];
p = 0;
while (2 * p + 1 < i) {
c = 2 * p + 1;
if (c + 1 < i && a[c] > a[c + 1]) {
c = c + 1;
}
if (elt <= a[c]) {
break;
}
a[p] = a[c];
p = c;
}
a[p] = elt;
}Priority Queues Using Heaps
Descending Priority Queue (Max Heap)
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
typedef struct priq {
int pq[MAX];
int n;
} PQ;
void init(PQ *pt) {
pt->n = 0;
}
void disp(PQ *pt) {
int i;
printf("Queue elements: ");
for (i = 0; i < pt->n; i++) {
printf("%d ", pt->pq[i]);
}
printf("\n");
}
int enqueue(PQ *pt, int e) {
int p, c;
if (pt->n >= MAX) return 0;
c = pt->n;
p = (c - 1) / 2;
while (c > 0 && pt->pq[p] < e) {
pt->pq[c] = pt->pq[p];
c = p;
p = (c - 1) / 2;
}
pt->pq[c] = e;
pt->n = pt->n + 1;
return 1;
}
int dequeue(PQ *pt, int *ele) {
int p, c;
if (pt->n == 0) return 0;
*ele = pt->pq[0];
int elt = pt->pq[pt->n - 1];
pt->n = pt->n - 1;
p = 0;
c = 2 * p + 1;
if (c + 1 < pt->n && pt->pq[c] < pt->pq[c + 1]) {
c = c + 1;
}
if (c >= pt->n) {
c = -1;
}
while (c >= 0 && elt < pt->pq[c]) {
pt->pq[p] = pt->pq[c];
p = c;
c = 2 * p + 1;
if (c + 1 < pt->n && pt->pq[c + 1] > pt->pq[c]) {
c = c + 1;
}
if (c >= pt->n) c = -1;
}
pt->pq[p] = elt;
return 1;
}Ascending Priority Queue (Min Heap)
int enqueue_min(PQ *pt, int e) {
int p, c;
if (pt->n >= MAX) return 0;
c = pt->n;
p = (c - 1) / 2;
while (c > 0 && pt->pq[p] > e) {
pt->pq[c] = pt->pq[p];
c = p;
p = (c - 1) / 2;
}
pt->pq[c] = e;
pt->n = pt->n + 1;
return 1;
}
int dequeue_min(PQ *pt, int *ele) {
int p, c;
if (pt->n == 0) return 0;
*ele = pt->pq[0];
int elt = pt->pq[pt->n - 1];
pt->n = pt->n - 1;
p = 0;
c = 2 * p + 1;
if (c + 1 < pt->n && pt->pq[c] > pt->pq[c + 1]) {
c = c + 1;
}
if (c >= pt->n) {
c = -1;
}
while (c >= 0 && elt > pt->pq[c]) {
pt->pq[p] = pt->pq[c];
p = c;
c = 2 * p + 1;
if (c + 1 < pt->n && pt->pq[c + 1] < pt->pq[c]) {
c = c + 1;
}
if (c >= pt->n) c = -1;
}
pt->pq[p] = elt;
return 1;
}