Data Structures: Queues, Trees, Graphs, and Searching Algorithms

Understanding Data Structures and Algorithms

8. Queues: FIFO Operations

A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. The element inserted first will be removed first, similar to people waiting in a line. It has two primary operations:

• enqueue(): Adds an element to the rear of the queue.
• dequeue(): Removes an element from the front of the queue.

Enqueue Operation Algorithm (Array-based):

1. Check if the queue is full (rear == size - 1).
2. If not full, increment rear.
3. Insert the new element at queue[rear].

Example:

if (rear == size - 1)
    printf("Queue Overflow");
else {
    rear++;
    queue[rear] = value;
}

Dequeue Operation Algorithm:

1. Check if the queue is empty (front > rear).
2. If not empty, retrieve the element at queue[front].
3. Increment front.

Example:

if (front > rear)
    printf("Queue Underflow");
else {
    value = queue[front];
    front++;
}

Types of Queues:

• Simple Queue: Follows FIFO. Insertion at the rear, deletion from the front.
• Circular Queue: Rear and front wrap around to utilize array space efficiently.
• Double-Ended Queue (Deque): Insertion and deletion are allowed from both ends.
• Priority Queue: Elements are inserted based on priority, not just order.

Queues are widely used in scheduling, buffering, and managing tasks in systems.

9. Trees: Hierarchical Data Representation

A tree is a non-linear data structure representing data hierarchically. It consists of nodes, with the topmost node called the root. Each node can have child nodes connected by edges. Nodes contain data and links to their children. Trees represent relationships like file systems and organizational charts.

Types of Trees:

• Binary Tree: Each node has at most two children (left and right).
• Binary Search Tree (BST): A binary tree where left children are smaller and right children are larger than the parent node.
• Complete Binary Tree: All levels are 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 are at the same level.
• Balanced Binary Tree: Height difference between left and right subtrees is at most 1.
• N-ary Tree: Each node can have up to N children.
• AVL Tree: A self-balancing binary search tree.

Trees are used in data compression, databases, compilers, and various applications.

10. Binary Tree Traversals

A Binary Tree is a tree where each node has at most two children: a left child and a right child. It forms the basis for structures like Binary Search Trees and Heaps. Each node contains data, a pointer to the left child, and a pointer to the right child.

Traversal Methods:

• Inorder Traversal (Left → Root → Right): Visits the left subtree, then the root, then the right subtree. Useful for obtaining elements in sorted order from a BST.
• Preorder Traversal (Root → Left → Right): Visits the root first, then the left subtree, then the right subtree. Used for copying trees and expression trees.
• Postorder Traversal (Left → Right → Root): Visits the left subtree, then the right subtree, then the root. Used for deleting trees and postfix expression evaluation.

Inorder Traversal Example (C):

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

Preorder Traversal Example (C):

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

Postorder Traversal Example (C):

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

11. Binary Search Trees (BST) Construction

A Binary Search Tree (BST) is a binary tree adhering to specific rules:

1. The left subtree of a node contains only nodes with values less than the node’s data.
2. The right subtree of a node contains only nodes with values greater than the node’s data.
3. Both left and right subtrees must also be binary search trees.

BSTs enable fast searching, insertion, and deletion, typically with O(log n) average time complexity for balanced trees.

Constructing a BST:

Data: 50, 30, 20, 40, 70, 60, 80

Insertion Process:

• 50 becomes the root.
• 30 is less than 50, goes left.
• 20 is less than 30, goes left of 30.
• 40 is greater than 30, goes right of 30.
• 70 is greater than 50, goes right of 50.
• 60 is less than 70, goes left of 70.
• 80 is greater than 70, goes right of 70.

Resulting BST Structure:

      50
     /  \
    30   70
   / \  / \
  20 40 60 80

This structure facilitates efficient searching and data organization.

12. AVL Trees and Rotations

An AVL Tree is a self-balancing Binary Search Tree (BST). The height difference between the left and right subtrees of any node (balance factor) is at most 1.

Balance Factor = height(left subtree) - height(right subtree)

Valid balance factors are -1, 0, or +1. If an insertion or deletion causes the balance factor to fall outside this range, rotations are performed to restore balance.

void DFS(int v) { visited[v] = 1; for (each unvisited neighbor u of v) DFS(u); }

Use Cases: Maze solving, topological sorting, cycle detection.

Breadth-First Search (BFS):

BFS explores level by level, visiting all neighbors of a node before moving to the next level. It uses a queue.

Steps:

1. Start at the source node.
2. Mark it visited and enqueue it.
3. Dequeue a node, visit its unvisited neighbors, and enqueue them.
4. Repeat until the queue is empty.

BFS Example:

void BFS(int v) {
    enqueue(v);
    visited[v] = 1;
    while (queue is not empty) {
        u = dequeue();
        for (each unvisited neighbor w of u)
            enqueue(w), mark visited;
    }
}

Use Case: Finding the shortest path in unweighted graphs, level-order traversal.

Key Difference: DFS goes deep; BFS goes wide. DFS uses a stack; BFS uses a queue.

15. Searching and Sorting Algorithms

Searching is finding an element (key) within a dataset. Sorting arranges elements in a specific order.

Searching:

• Linear Search: Checks elements sequentially. Time Complexity: O(n) worst case.
• Binary Search: Efficiently searches sorted data by repeatedly dividing the search interval. Time Complexity: O(log n).

Linear Search Program (C):

#include <stdio.h>

int main() {
    int arr[100], n, key, i, found = 0;
    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter %d elements:\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    printf("Enter element to search: ");
    scanf("%d", &key);

    for(i = 0; i < n; i++) {
        if(arr[i] == key) {
            printf("Element found at index %d\n", i);
            found = 1;
            break;
        }
    }

    if(!found)
        printf("Element not found\n");

    return 0;
}

Binary Search Program (C):

#include <stdio.h>

int main() {
    int arr[100], n, key, low, high, mid, i;
    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter %d sorted elements:\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    printf("Enter element to search: ");
    scanf("%d", &key);

    low = 0;
    high = n - 1;

    while(low <= high) {
        mid = (low + high) / 2;
        if(arr[mid] == key) {
            printf("Element found at index %d\n", mid);
            return 0;
        } else if(arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    printf("Element not found\n");
    return 0;
}

Sorting Algorithms:

• Bubble Sort: Compares and swaps adjacent elements. Time Complexity: O(n²) average/worst, O(n) best.
• Selection Sort: Finds the minimum element and swaps it to the correct position. Time Complexity: O(n²) always.
• Insertion Sort: Builds the sorted array by inserting elements one by one. Time Complexity: O(n²) average/worst, O(n) best.

Quick Sort:

A divide-and-conquer algorithm. It selects a pivot, partitions the array around the pivot, and recursively sorts the subarrays.

Example Logic:

• Array: 30, 10, 50, 20, 60
• Choose pivot = 30
• Rearrange → 10, 20, 30, 50, 60
• Recursively sort left (10, 20) and right (50, 60) parts.

Partition Function (C):

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1), temp;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++; 
            // swap arr[i] and arr[j]
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // swap arr[i+1] and arr[high] (pivot)
    temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

Quick Sort Function (C):

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);  // Left part
        quickSort(arr, pi + 1, high); // Right part
    }
}