8. Data Structures in C: Trees, Searching & Sorting Algorithms
Comprehensive Guide: Binary search trees, Linear Search, Binary Search, Bubble Sort, Quick Sort & Merge Sort complexities
Module 1: Binary Search Tree (BST) & Traversals
Hierarchical non-linear tree data structure maintaining sorted ordering.
🇬🇧 English Definition
A Binary Search Tree is a node-based binary tree data structure where left child nodes contain values smaller than the parent node and right child nodes contain larger values.
🇮🇳 Hinglish Definition
Binary Search Tree me har parent node ke chhote values Left Child me aur bade values Right Child me jate hai. Inorder traversal sorted output deta hai.
Core Concepts & Rules
- Inorder Traversal (Left, Root, Right): Prints nodes in ascending sorted order.
- Preorder Traversal: Root, Left, Right.
- Postorder Traversal: Left, Right, Root.
🔍 Line-by-Line Code Breakdown
- Line 1-5: Define struct TreeNode with data, left pointer, right pointer.
- Line 7-10: Inorder recursive traversal function.
struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
};
void inorder(struct TreeNode *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
struct TreeNode r = {20, NULL, NULL};
struct TreeNode l = {10, NULL, NULL};
r.left = &l;
printf("BST Inorder Traversal: ");
inorder(&r);
printf("\n");
return 0;
}Module 2: Sorting Algorithms in C (Bubble Sort & Binary Search)
Arranging data in ordered sequence and searching target elements efficiently.
🇬🇧 English Definition
Sorting algorithms reorder list elements in ascending/descending order, enabling fast O(log N) Binary Search execution.
🇮🇳 Hinglish Definition
Sorting se array order me arrange hota hai. Binary Search sorted array me target element ko super-fast O(log N) speed me dhundhta hai.
Core Concepts & Rules
- Bubble Sort Time Complexity: O(N^2) worst case.
- Binary Search Time Complexity: O(log N) requiring sorted input.
- Quick Sort / Merge Sort Time Complexity: O(N log N).
🔍 Line-by-Line Code Breakdown
- Line 2-8: Bubble Sort nested loop comparing adjacent elements and swapping if out of order.
- Line 9-11: Prints sorted array elements.
int main() {
int arr[4] = {40, 10, 30, 20};
int i, j, temp;
for (i = 0; i < 3; i++) {
for (j = 0; j < 3 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
printf("Sorted Array: %d %d %d %d\n", arr[0], arr[1], arr[2], arr[3]);
return 0;
}