Trees and Graphs in C Programming: A

Comprehensive Guide
Abstract
This document provides an exhaustive exploration of trees and graphs in C programming,
two fundamental non-linear data structures that form the cornerstone of advanced
algorithms and applications in computer science. Trees are hierarchical data structures
consisting of nodes connected by edges, with applications ranging from file systems and
organizational hierarchies to expression parsing and database indexing[44][46]. Graphs
represent relationships between objects through vertices and edges, enabling solutions to
complex problems like social networks, route optimization, and dependency
resolution[52]. This comprehensive guide examines implementation techniques for binary
trees, binary search trees, AVL trees, and various graph representations, essential
operations including traversals and searches, memory management considerations, and
advanced algorithms such as Dijkstra's shortest path and minimum spanning trees.
Through detailed explanations and over 45 code examples with explanatory comments,
readers will gain mastery of tree and graph manipulation essential for algorithm design,
systems programming, and technical interviews[44][49][51].

1. Introduction to Trees
1.1 What is a Tree?
A tree is a non-linear hierarchical data structure consisting of nodes connected by edges,
where each node contains a value and references to its child nodes[44][46]. Unlike linear
data structures such as arrays and linked lists, trees organize data in a parent-child
relationship, enabling efficient representation of hierarchical information. The topmost
node is called the root, and nodes without children are called leaves.
Trees provide several advantages over linear data structures:
• Hierarchical Organization: Natural representation of hierarchical relationships
• Efficient Searching: Binary search trees enable O(log n) search operations
• Dynamic Size: Trees can grow and shrink dynamically without pre-allocation
• Flexible Operations: Support for insertion, deletion, and traversal operations

1.2 Tree Terminology

Understanding tree terminology is essential for working with tree data structures:
• Node: A fundamental unit containing data and references to child nodes
• Root: The topmost node of the tree with no parent
• Edge: The connection between two nodes
• Parent: A node that has child nodes below it
• Child: A node directly connected below another node
• Leaf: A node with no children (also called external node)
 • Internal Node: A node with at least one child
• Siblings: Nodes sharing the same parent
• Ancestor: Any node on the path from root to the node
• Descendant: Any node reachable by moving downward from a node
• Subtree: A tree formed by a node and all its descendants
• Depth: The number of edges from root to the node
• Height: The number of edges on the longest path from the node to a leaf
• Level: The depth of a node plus one (root is at level 1)
• Degree: The number of children a node has

1.3 Types of Trees

Several specialized tree types serve different purposes:
• Binary Tree: Each node has at most two children (left and right)
• Binary Search Tree (BST): Binary tree with ordering property (left < parent < right)
• AVL Tree: Self-balancing BST maintaining height balance
• Complete Binary Tree: All levels filled except possibly the last, filled left to right
• Full Binary Tree: Every node has either 0 or 2 children
• Perfect Binary Tree: All internal nodes have two children and all leaves at same
level
• Heap: Complete binary tree satisfying heap property (min-heap or max-heap)
• B-Tree: Self-balancing tree for databases and file systems
• Trie: Tree for storing strings with shared prefixes

1.4 Tree Applications

Trees solve numerous real-world problems:
• File Systems: Directory structures organize files hierarchically
• Database Indexing: B-trees and B+ trees enable fast database queries
• Expression Parsing: Compiler parse trees represent program syntax
• Autocomplete: Tries efficiently store and search dictionary words
• Decision Making: Decision trees model choices and outcomes
• Network Routing: Spanning trees minimize network connections
• Compression: Huffman trees enable optimal data compression
• Game AI: Game trees evaluate possible moves and strategies

2. Binary Tree Implementation

2.1 Node Structure for Binary Tree
A binary tree node contains data and pointers to left and right children[47][51]:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Structure for binary tree node

struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Create a new node
struct Node* createNode(int value) {
// Allocate memory for new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}

// Initialize node
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;

return newNode;

2.2 Tree Traversal Methods

Tree traversal visits all nodes in a specific order. The three main depth-first traversals
are[51]:
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Preorder Traversal: Root -> Left -> Right
void preorderTraversal(struct Node* root) {
if (root == NULL) {
return;
}

// Process root first

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

// Recursively traverse left subtree

preorderTraversal(root->left);

// Recursively traverse right subtree

preorderTraversal(root->right);

}
// Inorder Traversal: Left -> Root -> Right
void inorderTraversal(struct Node* root) {
if (root == NULL) {
return;
}

// Recursively traverse left subtree

inorderTraversal(root->left);

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

// Recursively traverse right subtree

inorderTraversal(root->right);

}
// Postorder Traversal: Left -> Right -> Root
void postorderTraversal(struct Node* root) {
if (root == NULL) {
return;
}

// Recursively traverse left subtree

postorderTraversal(root->left);
 // Recursively traverse right subtree
postorderTraversal(root->right);

// Process root last

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

int main() {
// Create sample tree:
// 1
// /
// 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("Preorder Traversal: ");

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

printf("Inorder Traversal: ");

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

printf("Postorder Traversal: ");

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

return 0;

Output:
Preorder Traversal: 1 2 4 5 3
Inorder Traversal: 4 2 5 1 3
Postorder Traversal: 4 5 2 3 1

2.3 Level Order Traversal (Breadth-First)

Level order traversal visits nodes level by level using a queue:
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Queue implementation for level order traversal
#define MAX_SIZE 100

struct Queue {
struct Node* items[MAX_SIZE];
int front;
int rear;
};
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
int isEmpty(struct Queue* queue) {
return queue->front == -1;
}

void enqueue(struct Queue* queue, struct Node* node) {

if (isEmpty(queue)) {
queue->front = 0;
}
queue->rear++;
queue->items[queue->rear] = node;
}
struct Node* dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
return NULL;
}
struct Node* node = queue->items[queue->front];
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else {
queue->front++;
}
return node;
}
// Level Order Traversal
void levelOrderTraversal(struct Node* root) {
if (root == NULL) {
printf("Tree is empty\n");
return;
}

struct Queue queue;

initQueue(&queue);

// Start with root

enqueue(&queue, root);

printf("Level Order Traversal: ");

while (!isEmpty(&queue)) {
// Dequeue node and print it
struct Node* current = dequeue(&queue);
printf("%d ", current->data);

// Enqueue left child if exists

if (current->left != NULL) {
enqueue(&queue, current->left);
}

// Enqueue right child if exists

if (current->right != NULL) {
enqueue(&queue, current->right);
}
 }
printf("\n");

int main() {
// Create sample tree:
// 1
// /
// 2 3
// / \
// 4 5 6

struct Node* root = createNode(1);

root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->right = createNode(6);

levelOrderTraversal(root);

return 0;

2.4 Tree Properties: Height, Size, and Sum

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

struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Calculate height of tree (number of edges on longest path)
int height(struct Node* root) {
if (root == NULL) {
return -1; // Height of empty tree is -1
}

// Height = 1 + max(height of left, height of right)

int leftHeight = height(root->left);
int rightHeight = height(root->right);

return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);

}
// Calculate number of nodes in tree
int size(struct Node* root) {
if (root == NULL) {
return 0;
}

// Size = 1 (current node) + size of left + size of right

return 1 + size(root->left) + size(root->right);

}
// Calculate sum of all node values
int sum(struct Node* root) {
if (root == NULL) {
return 0;
}

// Sum = current value + sum of left + sum of right

return root->data + sum(root->left) + sum(root->right);

}
// Find maximum value in tree
int findMax(struct Node* root) {
if (root == NULL) {
return INT_MIN;
}

int leftMax = findMax(root->left);

int rightMax = findMax(root->right);
 int currentMax = root->data;

// Return maximum of current, left max, and right max

if (leftMax > currentMax) {
currentMax = leftMax;
}
if (rightMax > currentMax) {
currentMax = rightMax;
}

return currentMax;

// Count leaf nodes

int countLeaves(struct Node* root) {
if (root == NULL) {
return 0;
}

// If node is leaf (no children)

if (root->left == NULL && root->right == NULL) {
return 1;
}

// Count leaves in left and right subtrees

return countLeaves(root->left) + countLeaves(root->right);

int main() {
// Create sample tree:
// 10
// /
// 5 15
// / \
// 3 7 18

struct Node* root = createNode(10);

root->left = createNode(5);
root->right = createNode(15);
 root->left->left = createNode(3);
root->left->right = createNode(7);
root->right->right = createNode(18);

printf("Height of tree: %d\n", height(root));

printf("Number of nodes: %d\n", size(root));
printf("Sum of all nodes: %d\n", sum(root));
printf("Maximum value: %d\n", findMax(root));
printf("Number of leaves: %d\n", countLeaves(root));

return 0;

3. Binary Search Tree (BST)

3.1 BST Properties and Structure
A Binary Search Tree is a binary tree with the ordering property: for every node, all values
in the left subtree are less than the node's value, and all values in the right subtree are
greater[47][50]:

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Insert a value into BST

struct Node* insert(struct Node* root, int value) {
// If tree is empty, create new node
if (root == NULL) {
return createNode(value);
}
 // If value is less than root, insert in left subtree
if (value < root->data) {
root->left = insert(root->left, value);
}
// If value is greater than root, insert in right subtree
else if (value > root->data) {
root->right = insert(root->right, value);
}
// If value equals root, BST already contains it (no duplicates)

return root;

// Search for a value in BST

struct Node* search(struct Node* root, int value) {
// Base cases: root is null or value is at root
if (root == NULL || root->data == value) {
return root;
}

// Value is less than root, search left subtree

if (value < root->data) {
return search(root->left, value);
}

// Value is greater than root, search right subtree

return search(root->right, value);

// Inorder traversal (gives sorted order for BST)

void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
struct Node* root = NULL;
 // Insert values
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 60);
root = insert(root, 80);

printf("Inorder traversal (sorted): ");

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

// Search for values

int searchValue = 40;
struct Node* result = search(root, searchValue);
if (result != NULL) {
printf("Found %d in BST\n", searchValue);
} else {
printf("%d not found in BST\n", searchValue);
}

searchValue = 25;
result = search(root, searchValue);
if (result != NULL) {
printf("Found %d in BST\n", searchValue);
} else {
printf("%d not found in BST\n", searchValue);
}

return 0;

}
3.2 BST Deletion
Deletion in BST requires handling three cases[44]:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
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->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root;
}
// Find minimum value node in tree (leftmost node)
struct Node* findMin(struct Node* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}

// Delete a value from BST

struct Node* deleteNode(struct Node* root, int value) {
if (root == NULL) {
return root;
}

// Find the node to delete

if (value < root->data) {
root->left = deleteNode(root->left, value);
 } else if (value > root->data) {
root->right = deleteNode(root->right, value);
} else {
// Node found, perform deletion

// Case 1: Node has no children (leaf node)

if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}

// Case 2: Node has one 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: Node has two children

// Find inorder successor (minimum in right subtree)
struct Node* temp = findMin(root->right);

// Copy successor's value to current node

root->data = temp->data;

// Delete the successor

root->right = deleteNode(root->right, temp->data);
}

return root;

void inorder(struct Node* root) {

if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
struct Node* root = NULL;

root = insert(root, 50);

root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 60);
root = insert(root, 80);

printf("Original BST: ");

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

printf("\nDeleting 20 (leaf node)\n");

root = deleteNode(root, 20);
printf("After deletion: ");
inorder(root);
printf("\n");

printf("\nDeleting 30 (node with one child)\n");

root = deleteNode(root, 30);
printf("After deletion: ");
inorder(root);
printf("\n");

printf("\nDeleting 50 (node with two children)\n");

root = deleteNode(root, 50);
printf("After deletion: ");
inorder(root);
printf("\n");
 return 0;

3.3 BST Validation

Check if a binary tree is a valid BST:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Helper function to validate BST with range constraints

bool isBSTUtil(struct Node* root, int min, int max) {
// Empty tree is BST
if (root == NULL) {
return true;
}

// Check if current node violates min/max constraint

if (root->data <= min || root->data >= max) {
return false;
}

// Recursively check left and right subtrees with updated ranges

return isBSTUtil(root->left, min, root->data) &&
isBSTUtil(root->right, root->data, max);

}
// Check if binary tree is a valid BST
bool isBST(struct Node* root) {
return isBSTUtil(root, INT_MIN, INT_MAX);
}
int main() {
// Valid BST
struct Node* root1 = createNode(10);
root1->left = createNode(5);
root1->right = createNode(15);
root1->left->left = createNode(2);
root1->left->right = createNode(7);

printf("Tree 1 is %s\n", isBST(root1) ? "a valid BST" : "NOT a valid BST");

// Invalid BST
struct Node* root2 = createNode(10);
root2->left = createNode(5);
root2->right = createNode(15);
root2->right->left = createNode(6); // Violates BST property
root2->right->right = createNode(20);

printf("Tree 2 is %s\n", isBST(root2) ? "a valid BST" : "NOT a valid BST");

return 0;

3.4 Lowest Common Ancestor in BST

Find the lowest common ancestor of two nodes:
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
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->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root;
}

// Find Lowest Common Ancestor in BST

struct Node* findLCA(struct Node* root, int n1, int n2) {
if (root == NULL) {
return NULL;
}

// If both n1 and n2 are smaller than root, LCA is in left subtree

if (root->data > n1 && root->data > n2) {
return findLCA(root->left, n1, n2);
}

// If both n1 and n2 are greater than root, LCA is in right subtree

if (root->data < n1 && root->data < n2) {
return findLCA(root->right, n1, n2);
}

// If one is smaller and one is greater, root is LCA

return root;

int main() {
struct Node* root = NULL;

root = insert(root, 20);

root = insert(root, 10);
root = insert(root, 30);
root = insert(root, 5);
root = insert(root, 15);
 root = insert(root, 25);
root = insert(root, 35);

int n1 = 5, n2 = 15;
struct Node* lca = findLCA(root, n1, n2);
printf("LCA of %d and %d is: %d\n", n1, n2, lca->data);

n1 = 5;
n2 = 35;
lca = findLCA(root, n1, n2);
printf("LCA of %d and %d is: %d\n", n1, n2, lca->data);

n1 = 10;
n2 = 15;
lca = findLCA(root, n1, n2);
printf("LCA of %d and %d is: %d\n", n1, n2, lca->data);

return 0;

4. AVL Trees (Self-Balancing BST)

4.1 AVL Tree Properties
An AVL tree is a self-balancing BST where the height difference between left and right
subtrees cannot exceed 1 for any node[50][53]:

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
int height; // Height of node
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1; // New node is at height 1
return newNode;
}
// Get height of node
int getHeight(struct Node* node) {
if (node == NULL) {
return 0;
}
return node->height;
}

// Get maximum of two integers

int max(int a, int b) {
return (a > b) ? a : b;
}
// Calculate balance factor of node
int getBalance(struct Node* node) {
if (node == NULL) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}

4.2 AVL Tree Rotations

Four types of rotations restore balance[50]:
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* left;
struct Node* right;
int height;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1;
return newNode;
}
int getHeight(struct Node* node) {
if (node == NULL) return 0;
return node->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
int getBalance(struct Node* node) {
if (node == NULL) return 0;
return getHeight(node->left) - getHeight(node->right);
}

// Right rotation
struct Node* rightRotate(struct Node* y) {
struct Node* x = y->left;
struct Node* T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

return x; // New root

// Left rotation
struct Node* leftRotate(struct Node* x) {
struct Node* y = x->right;
struct Node* T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

return y; // New root

}
// Insert node in AVL tree
struct Node* insert(struct Node* node, int value) {
// 1. Perform standard BST insertion
if (node == NULL) {
return createNode(value);
}

if (value < node->data) {

node->left = insert(node->left, value);
} else if (value > node->data) {
node->right = insert(node->right, value);
} else {
return node; // Duplicate values not allowed
}

// 2. Update height of ancestor node

node->height = 1 + max(getHeight(node->left), getHeight(node->right));

// 3. Get balance factor

int balance = getBalance(node);

// 4. If unbalanced, perform rotations

// Left Left Case

if (balance > 1 && value < node->left->data) {
return rightRotate(node);
}

// Right Right Case

if (balance < -1 && value > node->right->data) {
return leftRotate(node);
}

// Left Right Case

if (balance > 1 && value > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
 // Right Left Case
if (balance < -1 && value < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}

return node;

// Inorder traversal
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
// Preorder traversal (shows structure)
void preorder(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
int main() {
struct Node* root = NULL;

// Insert values
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);

printf("Preorder traversal of AVL tree: ");

preorder(root);
printf("\n");
 printf("Inorder traversal of AVL tree: ");
inorder(root);
printf("\n");

return 0;

5. Tree Problems and Algorithms

5.1 Diameter of Binary Tree
Find the longest path between any two nodes[51]:

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

int maxDiameter = 0;
// Calculate height and update diameter
int height(struct Node* root) {
if (root == NULL) {
return 0;
}

// Get heights of left and right subtrees

int leftHeight = height(root->left);
int rightHeight = height(root->right);

// Diameter through this node

int diameter = leftHeight + rightHeight;
 // Update maximum diameter
if (diameter > maxDiameter) {
maxDiameter = diameter;
}

// Return height
return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);

int diameterOfBinaryTree(struct Node* root) {

maxDiameter = 0;
height(root);
return maxDiameter;
}
int main() {
// Create tree:
// 1
// /
// 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);

int diameter = diameterOfBinaryTree(root);

printf("Diameter of binary tree: %d\n", diameter);

return 0;

5.2 Check if Two Trees are Identical

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Check if two trees are identical

bool areIdentical(struct Node* root1, struct Node* root2) {
// Both trees are empty
if (root1 == NULL && root2 == NULL) {
return true;
}

// One tree is empty, other is not

if (root1 == NULL || root2 == NULL) {
return false;
}

// Check if current nodes match and recursively check subtrees

return (root1->data == root2->data) &&
areIdentical(root1->left, root2->left) &&
areIdentical(root1->right, root2->right);

int main() {
// Tree 1
struct Node* root1 = createNode(1);
root1->left = createNode(2);
root1->right = createNode(3);
root1->left->left = createNode(4);

// Tree 2 (identical to Tree 1)

struct Node* root2 = createNode(1);
root2->left = createNode(2);
root2->right = createNode(3);
 root2->left->left = createNode(4);

// Tree 3 (different from Tree 1)

struct Node* root3 = createNode(1);
root3->left = createNode(2);
root3->right = createNode(3);
root3->left->right = createNode(4);

printf("Tree 1 and Tree 2 are %s\n",

areIdentical(root1, root2) ? "identical" : "different");
printf("Tree 1 and Tree 3 are %s\n",
areIdentical(root1, root3) ? "identical" : "different");

return 0;

5.3 Invert Binary Tree

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

struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Invert binary tree (mirror)
struct Node* invertTree(struct Node* root) {
if (root == NULL) {
return NULL;
}

// Swap left and right children

struct Node* temp = root->left;
 root->left = root->right;
root->right = temp;

// Recursively invert subtrees

invertTree(root->left);
invertTree(root->right);

return root;

void inorder(struct Node* root) {

if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
// Create tree:
// 4
// /
// 2 7
// / \ /
// 1 3 6 9

struct Node* root = createNode(4);

root->left = createNode(2);
root->right = createNode(7);
root->left->left = createNode(1);
root->left->right = createNode(3);
root->right->left = createNode(6);
root->right->right = createNode(9);

printf("Original tree (inorder): ");

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

invertTree(root);

printf("Inverted tree (inorder): ");

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

return 0;

5.4 All Paths from Root to Leaves

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

struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Helper function to print all paths
void printPathsUtil(struct Node* root, int path[], int pathLen) {
if (root == NULL) {
return;
}

// Add current node to path

path[pathLen] = root->data;
pathLen++;

// If leaf node, print path

if (root->left == NULL && root->right == NULL) {
for (int i = 0; i < pathLen; i++) {
printf("%d", path[i]);
if (i < pathLen - 1) {
printf(" -> ");
}
 }
printf("\n");
} else {
// Recursively process left and right subtrees
printPathsUtil(root->left, path, pathLen);
printPathsUtil(root->right, path, pathLen);
}

// Print all root-to-leaf paths

void printPaths(struct Node* root) {
int path[1000];
printPathsUtil(root, path, 0);
}
int main() {
// Create tree:
// 1
// /
// 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("All root-to-leaf paths:\n");

printPaths(root);

return 0;

5.5 Maximum Path Sum

Find the maximum path sum in a binary tree:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) return NULL;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

int maxSum = INT_MIN;

// Helper function to calculate max path sum
int maxPathSumUtil(struct Node* root) {
if (root == NULL) {
return 0;
}

// Get maximum path sums from left and right subtrees

int leftSum = maxPathSumUtil(root->left);
int rightSum = maxPathSumUtil(root->right);

// Maximum path sum passing through current node

int maxSingle = (leftSum > rightSum ? leftSum : rightSum) + root->data;

// Maximum path sum with current node as highest point

int maxTop = leftSum + rightSum + root->data;

// Update global maximum

if (maxTop > maxSum) {
maxSum = maxTop;
}
if (maxSingle > maxSum) {
maxSum = maxSingle;
}

// Return maximum sum for single path

return maxSingle > 0 ? maxSingle : 0;
}
int maxPathSum(struct Node* root) {
maxSum = INT_MIN;
maxPathSumUtil(root);
return maxSum;
}

int main() {
// Create tree:
// -10
// /
// 9 20
// /
// 15 7

struct Node* root = createNode(-10);

root->left = createNode(9);
root->right = createNode(20);
root->right->left = createNode(15);
root->right->right = createNode(7);

printf("Maximum path sum: %d\n", maxPathSum(root));

return 0;

6. Introduction to Graphs
6.1 What is a Graph?
A graph is a non-linear data structure consisting of vertices (nodes) connected by edges,
representing relationships between objects[52]. Unlike trees, graphs can contain cycles and
have no hierarchical structure. Graphs model complex networks in computer science, from
social connections to transportation systems.

Graph Components:
• Vertex (Node): A fundamental unit representing an entity
• Edge: A connection between two vertices
• Adjacent Vertices: Vertices connected by an edge
• Degree: Number of edges connected to a vertex
• Path: Sequence of vertices connected by edges
• Cycle: Path that starts and ends at the same vertex
• Connected Graph: Path exists between every pair of vertices
• Weighted Graph: Edges have associated weights or costs
6.2 Types of Graphs
• Undirected Graph: Edges have no direction (symmetric relationship)
• Directed Graph (Digraph): Edges have direction (one-way relationship)
• Weighted Graph: Edges have weights representing costs or distances
• Unweighted Graph: All edges have equal weight
• Cyclic Graph: Contains at least one cycle
• Acyclic Graph: Contains no cycles (DAG - Directed Acyclic Graph)
• Complete Graph: Every vertex connected to every other vertex
• Bipartite Graph: Vertices divided into two sets with edges only between sets

6.3 Graph Applications

• Social Networks: Modeling friendships and connections
• Maps and Navigation: Finding shortest routes between locations
• Computer Networks: Network topology and routing protocols
• Recommendation Systems: Suggesting products or content
• Dependency Resolution: Build systems and package managers
• Web Crawling: Following hyperlinks between web pages
• Circuit Design: Electronic circuit analysis
• Resource Allocation: Scheduling and optimization problems

7. Graph Representation
7.1 Adjacency Matrix
An adjacency matrix is a 2D array where matrix[i][j] = 1 indicates an edge from vertex i to
vertex j[52]:
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 10
// Graph structure using adjacency matrix
struct Graph {
int numVertices;
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
};
// Initialize graph
void initGraph(struct Graph* graph, int vertices) {
graph->numVertices = vertices;

// Initialize all edges to 0 (no edges)

for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph->adjMatrix[i][j] = 0;
 }
}

// Add edge (undirected graph)

void addEdge(struct Graph* graph, int src, int dest) {
if (src >= 0 && src < graph->numVertices &&
dest >= 0 && dest < graph->numVertices) {
// For undirected graph, add edge in both directions
graph->adjMatrix[src][dest] = 1;
graph->adjMatrix[dest][src] = 1;
}
}
// Add directed edge
void addDirectedEdge(struct Graph* graph, int src, int dest) {
if (src >= 0 && src < graph->numVertices &&
dest >= 0 && dest < graph->numVertices) {
graph->adjMatrix[src][dest] = 1;
}
}
// Display adjacency matrix
void displayMatrix(struct Graph* graph) {
printf("Adjacency Matrix:\n");
printf(" ");
for (int i = 0; i < graph->numVertices; i++) {
printf("%d ", i);
}
printf("\n");

for (int i = 0; i < graph->numVertices; i++) {

printf("%d: ", i);
for (int j = 0; j < graph->numVertices; j++) {
printf("%d ", graph->adjMatrix[i][j]);
}
printf("\n");
}

}
int main() {
struct Graph graph;
initGraph(&graph, 5);
 // Add edges
addEdge(&graph, 0, 1);
addEdge(&graph, 0, 4);
addEdge(&graph, 1, 2);
addEdge(&graph, 1, 3);
addEdge(&graph, 1, 4);
addEdge(&graph, 2, 3);
addEdge(&graph, 3, 4);

displayMatrix(&graph);

return 0;

7.2 Adjacency List

An adjacency list uses an array of linked lists, where each list contains the neighbors of a
vertex[52]:

#include <stdio.h>
#include <stdlib.h>
// Node in adjacency list
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// Adjacency list
struct AdjList {
struct AdjListNode* head;
};

// Graph structure
struct Graph {
int numVertices;
struct AdjList* array;
};
// Create a new adjacency list node
struct AdjListNode* createNode(int dest) {
struct AdjListNode* newNode =
(struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// Create a graph with V vertices
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;

// Create array of adjacency lists

graph->array = (struct AdjList*)malloc(vertices * sizeof(struct AdjList));

// Initialize each adjacency list as empty

for (int i = 0; i < vertices; i++) {
graph->array[i].head = NULL;
}

return graph;

}
// Add edge to undirected graph
void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct AdjListNode* newNode = createNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

// Add edge from dest to src (undirected)

newNode = createNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;

}
// Add directed edge
void addDirectedEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = createNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}

// Display adjacency list

void displayGraph(struct Graph* graph) {
printf("Adjacency List:\n");
for (int i = 0; i < graph->numVertices; i++) {
struct AdjListNode* current = graph->array[i].head;
printf("%d: ", i);
while (current != NULL) {
printf("%d -> ", current->dest);
current = current->next;
}
printf("NULL\n");
}
}
int main() {
struct Graph* graph = createGraph(5);

addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);

displayGraph(graph);

return 0;

7.3 Weighted Graph Representation

#include <stdio.h>
#include <stdlib.h>
// Node in adjacency list with weight
struct AdjListNode {
int dest;
int weight;
struct AdjListNode* next;
};

struct AdjList {
struct AdjListNode* head;
};
struct Graph {
int numVertices;
struct AdjList* array;
};
struct AdjListNode* createNode(int dest, int weight) {
struct AdjListNode* newNode =
(struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->array = (struct AdjList*)malloc(vertices * sizeof(struct AdjList));

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

graph->array[i].head = NULL;
}

return graph;

}
// Add weighted edge
void addWeightedEdge(struct Graph* graph, int src, int dest, int weight) {
// Add edge from src to dest with weight
struct AdjListNode* newNode = createNode(dest, weight);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

// Add edge from dest to src (undirected)

newNode = createNode(src, weight);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;

}
void displayWeightedGraph(struct Graph* graph) {
printf("Weighted Adjacency List:\n");
for (int i = 0; i < graph->numVertices; i++) {
struct AdjListNode* current = graph->array[i].head;
printf("%d: ", i);
while (current != NULL) {
printf("(%d, w=%d) -> ", current->dest, current->weight);
current = current->next;
}
printf("NULL\n");
}
}
int main() {
struct Graph* graph = createGraph(4);

addWeightedEdge(graph, 0, 1, 5);
addWeightedEdge(graph, 0, 2, 3);
addWeightedEdge(graph, 1, 2, 2);
addWeightedEdge(graph, 1, 3, 6);
addWeightedEdge(graph, 2, 3, 7);

displayWeightedGraph(graph);

return 0;

8. Graph Traversal Algorithms

8.1 Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct AdjListNode {
int dest;
struct AdjListNode* next;
};
struct AdjList {
struct AdjListNode* head;
};
struct Graph {
int numVertices;
struct AdjList* array;
};

struct AdjListNode* createNode(int dest) {

struct AdjListNode* newNode =
(struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->array = (struct AdjList*)malloc(vertices * sizeof(struct AdjList));

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

graph->array[i].head = NULL;
}

return graph;

}
void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = createNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

newNode = createNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;

}
// DFS utility function
void DFSUtil(struct Graph* graph, int vertex, bool visited[]) {
// Mark current vertex as visited
visited[vertex] = true;
printf("%d ", vertex);

// Traverse all adjacent vertices

struct AdjListNode* current = graph->array[vertex].head;
while (current != NULL) {
int adjVertex = current->dest;
if (!visited[adjVertex]) {
DFSUtil(graph, adjVertex, visited);
}
current = current->next;
}
}
// Perform DFS traversal from given start vertex
void DFS(struct Graph* graph, int startVertex) {
// Create visited array
bool* visited = (bool*)calloc(graph->numVertices, sizeof(bool));

printf("DFS Traversal starting from vertex %d: ", startVertex);

DFSUtil(graph, startVertex, visited);
printf("\n");

free(visited);

}
int main() {
struct Graph* graph = createGraph(6);

addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 4);
addEdge(graph, 3, 5);
addEdge(graph, 4, 5);

DFS(graph, 0);

return 0;

8.2 Breadth-First Search (BFS)

BFS explores all neighbors at current depth before moving to next level:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct AdjListNode {
int dest;
struct AdjListNode* next;
};
struct AdjList {
struct AdjListNode* head;
};
struct Graph {
int numVertices;
struct AdjList* array;
};

struct AdjListNode* createNode(int dest) {

struct AdjListNode* newNode =
(struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->array = (struct AdjList*)malloc(vertices * sizeof(struct AdjList));

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

graph->array[i].head = NULL;
}

return graph;

}
void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = createNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

newNode = createNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;

}
// Queue for BFS
#define MAX_SIZE 100
struct Queue {
int items[MAX_SIZE];
int front;
int rear;
};
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}

int isEmpty(struct Queue* queue) {

return queue->front == -1;
}
void enqueue(struct Queue* queue, int value) {
if (isEmpty(queue)) {
queue->front = 0;
}
queue->rear++;
queue->items[queue->rear] = value;
}
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
return -1;
}
int value = queue->items[queue->front];
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else {
queue->front++;
}
return value;
}

// Perform BFS traversal

void BFS(struct Graph* graph, int startVertex) {
// Create visited array
bool* visited = (bool*)calloc(graph->numVertices, sizeof(bool));

// Create queue
struct Queue queue;
initQueue(&queue);

// Mark start vertex as visited and enqueue

visited[startVertex] = true;
enqueue(&queue, startVertex);

printf("BFS Traversal starting from vertex %d: ", startVertex);

 while (!isEmpty(&queue)) {
// Dequeue vertex and print
int currentVertex = dequeue(&queue);
printf("%d ", currentVertex);

// Visit all adjacent vertices

struct AdjListNode* current = graph->array[currentVertex].head;
while (current != NULL) {
int adjVertex = current->dest;
if (!visited[adjVertex]) {
visited[adjVertex] = true;
enqueue(&queue, adjVertex);
}
current = current->next;
}
}
printf("\n");

free(visited);

int main() {
struct Graph* graph = createGraph(6);

addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 4);
addEdge(graph, 3, 5);
addEdge(graph, 4, 5);

BFS(graph, 0);

return 0;

}
8.3 Cycle Detection in Undirected Graph
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
struct AdjList {
struct AdjListNode* head;
};

struct Graph {
int numVertices;
struct AdjList* array;
};
struct AdjListNode* createNode(int dest) {
struct AdjListNode* newNode =
(struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->array = (struct AdjList*)malloc(vertices * sizeof(struct AdjList));

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

graph->array[i].head = NULL;
}

return graph;

}
void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = createNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

newNode = createNode(src);
newNode->next = graph->array[dest].head;
 graph->array[dest].head = newNode;

// DFS utility to detect cycle

bool hasCycleUtil(struct Graph* graph, int vertex, bool visited[], int parent) {
visited[vertex] = true;

// Check all adjacent vertices

struct AdjListNode* current = graph->array[vertex].head;
while (current != NULL) {
int adjVertex = current->dest;

// If adjacent vertex not visited, recurse

if (!visited[adjVertex]) {
if (hasCycleUtil(graph, adjVertex, visited, vertex)) {
return true;
}
}
// If adjacent is visited and not parent, cycle exists
else if (adjVertex != parent) {
return true;
}

current = current->next;
}

return false;

// Check if graph has cycle

bool hasCycle(struct Graph* graph) {
bool* visited = (bool*)calloc(graph->numVertices, sizeof(bool));

// Check for cycle in each component

for (int i = 0; i < graph->numVertices; i++) {
if (!visited[i]) {
if (hasCycleUtil(graph, i, visited, -1)) {
free(visited);
 return true;
}
}
}

free(visited);
return false;

int main() {
// Graph with cycle
struct Graph* graph1 = createGraph(5);
addEdge(graph1, 0, 1);
addEdge(graph1, 1, 2);
addEdge(graph1, 2, 3);
addEdge(graph1, 3, 4);
addEdge(graph1, 4, 1); // Creates cycle

printf("Graph 1 %s a cycle\n", hasCycle(graph1) ? "has" : "does not have");

// Graph without cycle (tree)

struct Graph* graph2 = createGraph(5);
addEdge(graph2, 0, 1);
addEdge(graph2, 0, 2);
addEdge(graph2, 1, 3);
addEdge(graph2, 1, 4);

printf("Graph 2 %s a cycle\n", hasCycle(graph2) ? "has" : "does not have");

return 0;

9. Shortest Path Algorithms

9.1 Dijkstra's Algorithm
Find shortest paths from source to all vertices in weighted graph[49]:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_VERTICES 10

struct Graph {
int numVertices;
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
};
void initGraph(struct Graph* graph, int vertices) {
graph->numVertices = vertices;
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph->adjMatrix[i][j] = 0;
}
}
}
void addWeightedEdge(struct Graph* graph, int src, int dest, int weight) {
graph->adjMatrix[src][dest] = weight;
graph->adjMatrix[dest][src] = weight; // Undirected
}

// Find vertex with minimum distance

int minDistance(int dist[], bool visited[], int vertices) {
int min = INT_MAX;
int minIndex = -1;

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

if (!visited[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}

return minIndex;

// Dijkstra's shortest path algorithm

void dijkstra(struct Graph* graph, int src) {
int dist[MAX_VERTICES]; // Shortest distances
bool visited[MAX_VERTICES]; // Visited vertices

// Initialize distances as infinite and visited as false

for (int i = 0; i < graph->numVertices; i++) {
 dist[i] = INT_MAX;
visited[i] = false;
}

// Distance from source to itself is 0

dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < graph->numVertices - 1; count++) {
// Pick minimum distance vertex not yet processed
int u = minDistance(dist, visited, graph->numVertices);

if (u == -1) break; // No more reachable vertices

visited[u] = true;

// Update distances of adjacent vertices

for (int v = 0; v < graph->numVertices; v++) {
// Update dist[v] if:
// - v is not visited
// - there is edge from u to v
// - path through u is shorter
if (!visited[v] && graph->adjMatrix[u][v] &&
dist[u] != INT_MAX &&
dist[u] + graph->adjMatrix[u][v] < dist[v]) {
dist[v] = dist[u] + graph->adjMatrix[u][v];
}
}
}

// Print results
printf("Vertex\tDistance from Source %d\n", src);
for (int i = 0; i < graph->numVertices; i++) {
printf("%d\t", i);
if (dist[i] == INT_MAX) {
printf("INF\n");
} else {
printf("%d\n", dist[i]);
 }
}

int main() {
struct Graph graph;
initGraph(&graph, 6);

addWeightedEdge(&graph, 0, 1, 4);
addWeightedEdge(&graph, 0, 2, 3);
addWeightedEdge(&graph, 1, 2, 1);
addWeightedEdge(&graph, 1, 3, 2);
addWeightedEdge(&graph, 2, 3, 4);
addWeightedEdge(&graph, 3, 4, 2);
addWeightedEdge(&graph, 4, 5, 6);

dijkstra(&graph, 0);

return 0;

9.2 Bellman-Ford Algorithm

Handles negative edge weights and detects negative cycles[49]:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Edge structure
struct Edge {
int src;
int dest;
int weight;
};
// Graph structure
struct Graph {
int numVertices;
int numEdges;
struct Edge* edges;
};
struct Graph* createGraph(int vertices, int edges) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->numEdges = edges;
graph->edges = (struct Edge*)malloc(edges * sizeof(struct Edge));
return graph;
}
// Bellman-Ford algorithm
void bellmanFord(struct Graph* graph, int src) {
int V = graph->numVertices;
int E = graph->numEdges;
int dist[V];

// Initialize distances as infinite

for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
}
dist[src] = 0;

// Relax all edges V-1 times

for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edges[j].src;
int v = graph->edges[j].dest;
int weight = graph->edges[j].weight;

if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {

dist[v] = dist[u] + weight;
}
}
}

// Check for negative weight cycles

bool hasNegativeCycle = false;
for (int j = 0; j < E; j++) {
int u = graph->edges[j].src;
int v = graph->edges[j].dest;
int weight = graph->edges[j].weight;

if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {

 hasNegativeCycle = true;
printf("Graph contains negative weight cycle\n");
break;
}
}

if (!hasNegativeCycle) {
printf("Vertex\tDistance from Source %d\n", src);
for (int i = 0; i < V; i++) {
printf("%d\t", i);
if (dist[i] == INT_MAX) {
printf("INF\n");
} else {
printf("%d\n", dist[i]);
}
}
}

int main() {
int V = 5; // Number of vertices
int E = 8; // Number of edges

struct Graph* graph = createGraph(V, E);

// Add edges
graph->edges[0].src = 0; graph->edges[0].dest = 1; graph->edges[0].weight = -1;
graph->edges[1].src = 0; graph->edges[1].dest = 2; graph->edges[1].weight = 4;
graph->edges[2].src = 1; graph->edges[2].dest = 2; graph->edges[2].weight = 3;
graph->edges[3].src = 1; graph->edges[3].dest = 3; graph->edges[3].weight = 2;
graph->edges[4].src = 1; graph->edges[4].dest = 4; graph->edges[4].weight = 2;
graph->edges[5].src = 3; graph->edges[5].dest = 2; graph->edges[5].weight = 5;
graph->edges[6].src = 3; graph->edges[6].dest = 1; graph->edges[6].weight = 1;
graph->edges[7].src = 4; graph->edges[7].dest = 3; graph->edges[7].weight = -3;

bellmanFord(graph, 0);
 return 0;

10. Minimum Spanning Tree Algorithms

10.1 Prim's Algorithm
Find minimum spanning tree for connected weighted graph[49]:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_VERTICES 10
struct Graph {
int numVertices;
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
};

void initGraph(struct Graph* graph, int vertices) {

graph->numVertices = vertices;
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph->adjMatrix[i][j] = 0;
}
}
}
void addWeightedEdge(struct Graph* graph, int src, int dest, int weight) {
graph->adjMatrix[src][dest] = weight;
graph->adjMatrix[dest][src] = weight;
}
// Find vertex with minimum key value
int minKey(int key[], bool mstSet[], int vertices) {
int min = INT_MAX;
int minIndex = -1;

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

if (!mstSet[v] && key[v] < min) {
min = key[v];
minIndex = v;
}
}
 return minIndex;

// Print MST
void printMST(int parent[], struct Graph* graph) {
printf("Edge\tWeight\n");
int totalWeight = 0;

for (int i = 1; i < graph->numVertices; i++) {

printf("%d - %d\t%d\n", parent[i], i,
graph->adjMatrix[i][parent[i]]);
totalWeight += graph->adjMatrix[i][parent[i]];
}

printf("Total weight of MST: %d\n", totalWeight);

// Prim's algorithm for MST

void primMST(struct Graph* graph) {
int parent[MAX_VERTICES]; // Array to store MST
int key[MAX_VERTICES]; // Key values for picking minimum weight
bool mstSet[MAX_VERTICES]; // Vertices included in MST

// Initialize all keys as infinite

for (int i = 0; i < graph->numVertices; i++) {
key[i] = INT_MAX;
mstSet[i] = false;
}

// Start from vertex 0

key[0] = 0;
parent[0] = -1; // First node is root

// MST will have V vertices

for (int count = 0; count < graph->numVertices - 1; count++) {
// Pick minimum key vertex not in MST
int u = minKey(key, mstSet, graph->numVertices);
 if (u == -1) break;

mstSet[u] = true;

// Update key values of adjacent vertices

for (int v = 0; v < graph->numVertices; v++) {
// Update key[v] if:
// - edge u-v exists
// - v is not in MST
// - weight of u-v is less than current key[v]
if (graph->adjMatrix[u][v] && !mstSet[v] &&
graph->adjMatrix[u][v] < key[v]) {
parent[v] = u;
key[v] = graph->adjMatrix[u][v];
}
}
}

printMST(parent, graph);

int main() {
struct Graph graph;
initGraph(&graph, 5);

addWeightedEdge(&graph, 0, 1, 2);
addWeightedEdge(&graph, 0, 3, 6);
addWeightedEdge(&graph, 1, 2, 3);
addWeightedEdge(&graph, 1, 3, 8);
addWeightedEdge(&graph, 1, 4, 5);
addWeightedEdge(&graph, 2, 4, 7);
addWeightedEdge(&graph, 3, 4, 9);

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

primMST(&graph);

return 0;
}

10.2 Kruskal's Algorithm

Find MST by sorting edges and using union-find[49]:
#include <stdio.h>
#include <stdlib.h>

struct Edge {
int src;
int dest;
int weight;
};
struct Graph {
int numVertices;
int numEdges;
struct Edge* edges;
};
struct Graph* createGraph(int vertices, int edges) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->numEdges = edges;
graph->edges = (struct Edge*)malloc(edges * sizeof(struct Edge));
return graph;
}

// Union-Find (Disjoint Set) data structure

struct Subset {
int parent;
int rank;
};
// Find set of element i (with path compression)
int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
// Union of two sets (by rank)
void unionSets(struct Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);

// Attach smaller rank tree under root of higher rank tree

if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
 } else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}

// Compare function for qsort

int compareEdges(const void* a, const void* b) {
struct Edge* edgeA = (struct Edge*)a;
struct Edge* edgeB = (struct Edge*)b;
return edgeA->weight - edgeB->weight;
}
// Kruskal's algorithm for MST
void kruskalMST(struct Graph* graph) {
int V = graph->numVertices;
struct Edge result[V]; // Store MST edges
int e = 0; // Index for result[]
int i = 0; // Index for sorted edges

// Sort all edges in ascending order of weight

qsort(graph->edges, graph->numEdges, sizeof(graph->edges[0]), compareEdges)

// Create V subsets for union-find

struct Subset* subsets =
(struct Subset*)malloc(V * sizeof(struct Subset));

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

subsets[v].parent = v;
subsets[v].rank = 0;
}

// Number of edges in MST will be V-1

while (e < V - 1 && i < graph->numEdges) {
// Pick smallest edge
struct Edge nextEdge = graph->edges[i++];

int x = find(subsets, nextEdge.src);

int y = find(subsets, nextEdge.dest);
 // If including this edge doesn't cause cycle, include it
if (x != y) {
result[e++] = nextEdge;
unionSets(subsets, x, y);
}
}

// Print MST
printf("Minimum Spanning Tree (Kruskal's Algorithm):\n");
printf("Edge\tWeight\n");
int totalWeight = 0;

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

printf("%d - %d\t%d\n", result[i].src, result[i].dest,
result[i].weight);
totalWeight += result[i].weight;
}

printf("Total weight of MST: %d\n", totalWeight);

free(subsets);

int main() {
int V = 4; // Number of vertices
int E = 5; // Number of edges

struct Graph* graph = createGraph(V, E);

// Add edges
graph->edges[0].src = 0; graph->edges[0].dest = 1; graph->edges[0].weight = 10;
graph->edges[1].src = 0; graph->edges[1].dest = 2; graph->edges[1].weight = 6;
graph->edges[2].src = 0; graph->edges[2].dest = 3; graph->edges[2].weight = 5;
graph->edges[3].src = 1; graph->edges[3].dest = 3; graph->edges[3].weight = 15;
graph->edges[4].src = 2; graph->edges[4].dest = 3; graph->edges[4].weight = 4;

kruskalMST(graph);
 return 0;

11. Topological Sorting

Sort vertices of directed acyclic graph in linear order:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct AdjListNode {
int dest;
struct AdjListNode* next;
};

struct AdjList {
struct AdjListNode* head;
};
struct Graph {
int numVertices;
struct AdjList* array;
};
struct AdjListNode* createNode(int dest) {
struct AdjListNode* newNode =
(struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}

struct Graph* createGraph(int vertices) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->array = (struct AdjList*)malloc(vertices * sizeof(struct AdjList));

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

graph->array[i].head = NULL;
}

return graph;

}
void addDirectedEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = createNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}
// Stack for storing topological order
struct Stack {
int items[100];
int top;
};

void initStack(struct Stack* stack) {

stack->top = -1;
}
void push(struct Stack* stack, int value) {
stack->top++;
stack->items[stack->top] = value;
}
int pop(struct Stack* stack) {
if (stack->top == -1) {
return -1;
}
int value = stack->items[stack->top];
stack->top--;
return value;
}

int isEmpty(struct Stack* stack) {

return stack->top == -1;
}
// DFS utility for topological sort
void topologicalSortUtil(struct Graph* graph, int v, bool visited[],
struct Stack* stack) {
visited[v] = true;

// Recurse for all adjacent vertices

struct AdjListNode* current = graph->array[v].head;
while (current != NULL) {
int adjVertex = current->dest;
if (!visited[adjVertex]) {
topologicalSortUtil(graph, adjVertex, visited, stack);
}
current = current->next;
}
 // Push current vertex to stack after visiting all descendants
push(stack, v);

// Topological sort
void topologicalSort(struct Graph* graph) {
struct Stack stack;
initStack(&stack);

bool* visited = (bool*)calloc(graph->numVertices, sizeof(bool));

// Call utility function for all vertices

for (int i = 0; i < graph->numVertices; i++) {
if (!visited[i]) {
topologicalSortUtil(graph, i, visited, &stack);
}
}

// Print topological order

printf("Topological Sort: ");
while (!isEmpty(&stack)) {
printf("%d ", pop(&stack));
}
printf("\n");

free(visited);

int main() {
struct Graph* graph = createGraph(6);

addDirectedEdge(graph, 5, 2);
addDirectedEdge(graph, 5, 0);
addDirectedEdge(graph, 4, 0);
addDirectedEdge(graph, 4, 1);
addDirectedEdge(graph, 2, 3);
addDirectedEdge(graph, 3, 1);
 topologicalSort(graph);

return 0;

12. Performance Analysis and Best Practices

12.1 Time Complexity Comparison
Operation Binary Tree BST (Balanced)
Search O(n) O(log n)
Insert O(1) at known position O(log n)
Delete O(n) O(log n)
Traversal O(n) O(n)
Height O(n) O(log n)

Table 1: Tree operation complexities[44][47]

Graph Algorithm Time Complexity Space

DFS O(V + E) O(V)
BFS O(V + E) O(V)
Dijkstra O(V²) or O(E log V) O(V)
Bellman-Ford O(VE) O(V)
Prim's MST O(V²) or O(E log V) O(V)
Kruskal's MST O(E log E) O(V)
Topological Sort O(V + E) O(V)

Table 2: Graph algorithm complexities[49][52]

12.2 Space Complexity

• Adjacency Matrix: O(V²) - Efficient for dense graphs
• Adjacency List: O(V + E) - Efficient for sparse graphs
• Tree Height: O(log n) for balanced, O(n) for skewed
• Recursion Stack: O(h) where h is height for tree operations
12.3 Best Practices
• Choose Appropriate Representation: Use adjacency list for sparse graphs, matrix
for dense graphs
• Handle Memory Properly: Free all allocated nodes to prevent memory leaks
• Check for NULL: Always validate pointers before dereferencing
• Use Balanced Trees: AVL or Red-Black trees for guaranteed O(log n) operations
• Optimize Graph Algorithms: Use priority queues for Dijkstra, union-find for Kruskal
• Consider Edge Cases: Empty trees, single nodes, disconnected graphs
• Use Iterative When Possible: Avoid stack overflow with large trees
• Mark Visited Nodes: Prevent infinite loops in graph traversals

12.4 Common Pitfalls

• Memory Leaks: Not freeing tree/graph nodes after use
• Stack Overflow: Deep recursion in unbalanced trees
• NULL Pointer Dereference: Not checking for empty trees/graphs
• Infinite Loops: Not marking visited nodes in graph traversals
• Incorrect Rotations: AVL tree rotations must update heights correctly
• Cycle Handling: Not detecting cycles before processing DAGs
• Edge Weight Overflow: Large weights causing integer overflow
• Disconnected Components: Algorithms must handle multiple components

12.5 When to Use Trees vs Graphs

Use Trees when:
Hierarchical relationships (file systems, organization charts)
Need for ordered data (BST for searching)
Fast insertion and deletion required (balanced trees)
Implementing priority queues (heaps)
Expression parsing (parse trees)

Use Graphs when:

Modeling networks (social, computer, transportation)
Finding shortest paths or optimal routes
Detecting cycles or dependencies
Representing many-to-many relationships
Solving constraint satisfaction problems

13. Conclusion
Trees and graphs represent fundamental non-linear data structures that enable
sophisticated solutions to complex computational problems across diverse domains of
computer science[44][46][52]. Trees provide hierarchical organization essential for file
systems, database indexing, and expression evaluation, while graphs model relationships
in networks, maps, and dependency systems. Through this comprehensive guide, we have
explored implementation techniques from basic binary trees to self-balancing AVL trees,
and from simple graph representations to advanced algorithms like Dijkstra's shortest path
and Kruskal's minimum spanning tree.
Understanding the trade-offs between different representations—adjacency matrices
versus adjacency lists, recursive versus iterative implementations—enables informed
design decisions based on specific requirements[52]. The traversal algorithms covered—
preorder, inorder, postorder for trees, and DFS, BFS for graphs—form the foundation for
more sophisticated algorithms in artificial intelligence, compiler design, and network
optimization. Self-balancing trees like AVL trees demonstrate how algorithmic techniques
can maintain optimal performance characteristics even as data changes dynamically.
The practical problems explored—diameter of binary tree, BST validation, cycle detection,
topological sorting, shortest path finding—illustrate the versatility of trees and graphs in
solving real-world computational challenges[44][49][51]. The ability to implement efficient
graph algorithms such as Dijkstra, Bellman-Ford, Prim, and Kruskal demonstrates mastery
of both theoretical concepts and practical programming skills essential for technical
interviews and professional software development.

Mastery of trees and graphs forms the cornerstone of advanced algorithm design and data
structure knowledge. The over 45 code examples with explanatory comments provided in
this guide enable hands-on practice essential for developing algorithmic intuition. By
understanding these fundamental patterns—from basic tree operations to complex graph
algorithms—programmers develop the problem-solving capabilities necessary for tackling
increasingly sophisticated computational problems in systems programming, artificial
intelligence, network engineering, and beyond. Trees and graphs remain indispensable
tools in the modern software engineer's toolkit, providing elegant solutions to problems
ranging from organizing hierarchical data to optimizing complex network operations.

References
[44] Tree Data Structure. (2023, June 8). GeeksforGeeks. https://www.geeksforgeeks.org/dsa/t
ree-data-structure/
[46] Tree Data Structure. (2024, October 31). Programiz.
https://www.programiz.com/dsa/trees

[47] Binary Tree in C – Types and Implementation. (2022, September 27). Scaler Topics. http
s://www.scaler.com/topics/binary-tree-in-c/
[49] Graph Algorithms - C Implementations. (2017, August 25). GitHub. https://github.com/dip
pedrusk/graph-algorithms
[50] Section 05: Solutions - AVL Trees. (2024). University of Washington. https://courses.cs.wa
shington.edu/courses/cse373/24wi/sections/section04-solutions.pdf

[51] Understanding and Implementing Tree Data Structures in C. (2024, December 2).
Hashnode. https://alokgupta.hashnode.dev/understanding-and-implementing-tree-data-str
uctures-in-c
[52] Implementation of Graph in C. (2024, June 18). GeeksforGeeks. https://www.geeksforgee
ks.org/c/implementation-of-graph-in-c/
[53] Practice questions on Height balanced/AVL Tree. (2018, February 4). GeeksforGeeks. htt
ps://www.geeksforgeeks.org/dsa/practice-questions-height-balancedavl-tree/