Data Structures & Algorithms

Stack = A linear data structure following LIFO (Last In First Out) principle

Key Characteristics:

• Elements added/removed from one end only (TOP)
• Like a stack of plates

Basic Operations:

Applications:

• Function call management
• Expression evaluation
• Undo operations
• Browser back button

Push Operation:

Adds element to the top of stack

PUSH(stack, x):
  if (top == MAX-1)
    print 'Stack Overflow'
  else
    top = top + 1
    stack[top] = x

Pop Operation:

Removes and returns top element

POP(stack):
  if (top == -1)
    print 'Stack Underflow'
  else
    x = stack[top]
    top = top - 1
    return x

Key Points:

• Overflow: Trying to push when stack is full
• Underflow: Trying to pop when stack is empty
• Initial value of top = -1 (empty stack)

Static Array Implementation:

#define MAX 100
int stack[MAX];
int top = -1;

void push(int x) {
  if(top == MAX-1)
    printf("Overflow");
  else
    stack[++top] = x;
}

int pop() {
  if(top == -1)
    printf("Underflow");
  else
    return stack[top--];
}

Advantages:

✓ Simple implementation

✓ Fast access O(1)

✓ Memory efficient

Disadvantages:

✗ Fixed size (static)

✗ Can cause overflow

✗ Memory wastage if not fully used

Dynamic Stack using Linked List:

struct Node {
  int data;
  struct Node* next;
};
struct Node* top = NULL;

void push(int x) {
  Node* newNode = malloc(sizeof(Node));
  newNode->data = x;
  newNode->next = top;
  top = newNode;
}

int pop() {
  if(top == NULL)
    printf("Underflow");
  else {
    int x = top->data;
    Node* temp = top;
    top = top->next;
    free(temp);
    return x;
  }
}

Advantages:

✓ Dynamic size (no overflow)

✓ Memory allocated as needed

Disadvantages:

✗ Extra memory for pointers

✗ Slightly slower than array

Multiple Stacks in One Array:

Method 1: Fixed Division

• Divide array into n equal parts
• Stack i uses: [isize/n] to [(i+1)size/n - 1]
• Simple but wastes space

Method 2: Space Efficient (2 Stacks)

• Stack1 starts from index 0, grows right
• Stack2 starts from index n-1, grows left

int arr[MAX];
int top1 = -1, top2 = MAX;

void push1(int x) {
  if(top1 < top2 - 1)
    arr[++top1] = x;
}

void push2(int x) {
  if(top1 < top2 - 1)
    arr[--top2] = x;
}

Overflow condition: top1 + 1 == top2

Reversing List using Stack:

Algorithm:

• 1. Push all elements onto stack
• 2. Pop all elements back to list

void reverse(int arr[], int n) {
  Stack s;
  // Push all elements
  for(int i=0; i<n; i++)
    push(s, arr[i]);
  
  // Pop back to array
  for(int i=0; i<n; i++)
    arr[i] = pop(s);
}

Example:

Input: [1, 2, 3, 4, 5]

Stack after push: 5 (top) → 4 → 3 → 2 → 1

Output after pop: [5, 4, 3, 2, 1]

Time Complexity: O(n)

Space Complexity: O(n)

Factorial using Stack (Simulating Recursion):

Recursive: n! = n × (n-1)!

Stack-based approach:

int factorial(int n) {
  Stack s;
  int result = 1;
  
  // Push n to 1
  while(n > 0) {
    push(s, n);
    n--;
  }
  
  // Pop and multiply
  while(!isEmpty(s)) {
    result *= pop(s);
  }
  return result;
}

Example: 5!

Push: 5, 4, 3, 2, 1

Pop & Multiply: 1×2×3×4×5 = 120

Why Stack?

Simulates function call stack used in recursion

Infix to Postfix Conversion:

Infix: A + B * C

Postfix: A B C * +

Algorithm:

• 1. Scan left to right
• 2. If operand → output directly
• 3. If '(' → push to stack
• 4. If ')' → pop until '(' found
• 5. If operator → pop higher/equal precedence, then push
• 6. Pop remaining operators

Precedence: ^ > * / > + -

**Example: A + B * C**

Result: ABC*+

Postfix Expression Evaluation:

Algorithm:

• 1. Scan left to right
• 2. If operand → push to stack
• 3. If operator → pop two operands, apply operator, push result
• 4. Final result is top of stack

**Example: 2 3 4 * +**

Result: 14

Time Complexity: O(n)

Note: For operators, second popped = left operand

Tower of Hanoi:

Problem: Move n disks from source to destination using auxiliary peg

Rules:

• 1. Only one disk at a time
• 2. Larger disk cannot be on smaller disk
• 3. Only top disk can be moved

Recursive Solution:

TOH(n, source, dest, aux):
  if n == 1:
    move disk from source to dest
  else:
    TOH(n-1, source, aux, dest)
    move disk from source to dest
    TOH(n-1, aux, dest, source)

Number of moves: 2ⁿ - 1

Example for n=3:

Minimum moves = 2³ - 1 = 7

Time Complexity: O(2ⁿ)

Stack frames used: n (recursion depth)

Queue = Linear data structure following FIFO (First In First Out) principle

Key Characteristics:

• Insertion at REAR
• Deletion from FRONT
• Like a line at ticket counter

Basic Operations:

Applications:

• CPU scheduling
• Print spooling
• BFS traversal
• Keyboard buffer

Array-based Queue:

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int x) {
  if(rear == MAX-1)
    printf("Overflow");
  else {
    if(front == -1) front = 0;
    queue[++rear] = x;
  }
}

int dequeue() {
  if(front == -1 || front > rear)
    printf("Underflow");
  else
    return queue[front++];
}

Problem: After multiple operations, front moves right, wasting space

Solution: Circular Queue

Initial: front = rear = -1

After 1st enqueue: front = rear = 0

Queue using Two Stacks:

Method 1: Costly Enqueue

enqueue(x):
  while(s1 not empty)
    push(s2, pop(s1))
  push(s1, x)
  while(s2 not empty)
    push(s1, pop(s2))

dequeue():
  return pop(s1)

Method 2: Costly Dequeue (Efficient)

enqueue(x):
  push(s1, x)

dequeue():
  if(s2 empty)
    while(s1 not empty)
      push(s2, pop(s1))
  return pop(s2)

Time Complexity:

• Method 2: Amortized O(1) for both operations

Key Insight: Stack reverses order, two stacks restore it

Circular Queue:

Queue where last position connects back to first position

Advantage: Overcomes linear queue's space wastage

Implementation:

void enqueue(int x) {
  if((rear+1) % MAX == front)
    printf("Overflow");
  else {
    rear = (rear + 1) % MAX;
    queue[rear] = x;
    if(front == -1) front = 0;
  }
}

int dequeue() {
  if(front == -1)
    printf("Underflow");
  else {
    int x = queue[front];
    if(front == rear)
      front = rear = -1;
    else
      front = (front + 1) % MAX;
    return x;
  }
}

Full condition: (rear + 1) % MAX == front

Empty condition: front == -1

DeQueue (Double Ended Queue):

Elements can be added/removed from BOTH ends

Operations:

• insertFront(x)
• insertRear(x)
• deleteFront()
• deleteRear()

Types:

• 1. Input Restricted DeQueue
• Insert only at rear
• Delete from both ends

• 2. Output Restricted DeQueue
• Insert at both ends
• Delete only from front

Applications:

• Sliding window problems
• Palindrome checker
• Work stealing algorithm

Implementation: Usually as doubly linked list or circular array

Priority Queue:

Elements dequeued based on priority, not arrival order

Types:

• 1. Ascending Priority Queue
• Smallest priority dequeued first
• Min-heap implementation

• 2. Descending Priority Queue
• Largest priority dequeued first
• Max-heap implementation

Implementation Options:

Applications:

• CPU scheduling
• Dijkstra's algorithm
• Huffman coding
• Event-driven simulation

Round Robin Algorithm:

CPU scheduling where each process gets fixed time quantum in circular order

Uses Queue for implementation

Algorithm:

• 1. Add all processes to queue
• 2. Dequeue first process
• 3. Execute for time quantum
• 4. If not complete, enqueue again
• 5. Repeat until queue empty

Example:

Processes: P1(10), P2(5), P3(8)

Time Quantum: 4

...

Advantages:

• Fair CPU allocation
• No starvation

Linked List:

Linear data structure where elements are connected using pointers

Node Structure:

struct Node {
  int data;
  struct Node* next;
};

Key Features:

• Dynamic size
• Non-contiguous memory
• Each node → data + pointer to next

Types:

• 1. Single Linked List
• 2. Double Linked List
• 3. Circular Linked List
• 4. Header Linked List

Memory Representation:

[10|→] → [20|→] → [30|NULL]

Head pointer: Points to first node

Single Linked List Operations:

1. Insertion:

• At beginning: O(1)
• At end: O(n)
• At position: O(n)

2. Deletion:

• From beginning: O(1)
• From end: O(n)
• By value: O(n)

3. Traversal: O(n)

4. Search: O(n)

Insert at Beginning:

void insertBegin(int x) {
  Node* newNode = malloc(sizeof(Node));
  newNode->data = x;
  newNode->next = head;
  head = newNode;
}

Delete from Beginning:

void deleteBegin() {
  Node* temp = head;
  head = head->next;
  free(temp);
}

Reversing Single Linked List:

Iterative Method:

Node* reverse(Node* head) {
  Node *prev = NULL, *curr = head, *next;
  while(curr != NULL) {
    next = curr->next;  // Store next
    curr->next = prev;  // Reverse link
    prev = curr;        // Move prev
    curr = next;        // Move curr
  }
  return prev;  // New head
}

Example:

1→2→3→NULL becomes 3→2→1→NULL

Recursive Method:

Node* reverse(Node* head) {
  if(head==NULL || head->next==NULL)
    return head;
  Node* rest = reverse(head->next);
  head->next->next = head;
  head->next = NULL;
  return rest;
}

Time: O(n), Space: O(1) iterative, O(n) recursive

Advantages of Single Linked List:

✓ Dynamic Size - Grows/shrinks at runtime

✓ Efficient Insertion/Deletion - O(1) at beginning

✓ No Memory Wastage - Allocate as needed

✓ No Need for Contiguous Memory

✓ Easy Implementation of stacks/queues

Disadvantages:

✗ No Random Access - Must traverse O(n)

✗ Extra Memory - For pointers

✗ No Backward Traversal - Only forward

✗ Cache Unfriendly - Non-contiguous memory

✗ Risk of Memory Leaks - If not freed properly

Comparison with Array:

Circular Linked List:

Last node points back to first node (no NULL)

Structure:

[10] → [20] → [30] → [10] (back to first)

Advantages over SLL:

• Can reach any node from any node
• Useful for round-robin scheduling
• Continuous traversal possible

Traversal:

void traverse(Node* head) {
  Node* temp = head;
  do {
    printf("%d ", temp->data);
    temp = temp->next;
  } while(temp != head);
}

Applications:

• Round-robin scheduling
• Circular buffers
• Music playlist (loop)
• Multiplayer games (turns)

Doubly Linked List:

Each node has pointers to BOTH next and previous nodes

Structure:

struct Node {
  int data;
  struct Node* prev;
  struct Node* next;
};

Diagram:

NULL ← [10] ⟷ [20] ⟷ [30] → NULL

Advantages:

✓ Bidirectional traversal

✓ Easier deletion (don't need prev reference)

✓ Can be traversed forward and backward

Disadvantages:

✗ Extra memory for prev pointer

✗ More complex operations

Use Cases:

• Browser forward/back
• Undo/redo operations
• Music player prev/next

Header Linked List:

Special node (header) at the beginning that contains metadata

Types:

1. Grounded Header List:

• Last node points to NULL
• Header → Node1 → Node2 → NULL

2. Circular Header List:

• Last node points back to header
• Header → Node1 → Node2 → Header

Header Node Contains:

• Count of nodes
• Pointer to first/last node
• Other metadata

Advantages:

✓ Easy to track list size

✓ Uniform handling (no special case for empty list)

✓ Can store list properties

Example:

[Count=3|→] → [10] → [20] → [30] → NULL

Linear Search:

Search element by checking each item one by one

Algorithm:

int linearSearch(int arr[], int n, int key) {
  for(int i=0; i<n; i++) {
    if(arr[i] == key)
      return i;  // Found
  }
  return -1;  // Not found
}

Time Complexity:

• Best Case: O(1) - First element
• Worst Case: O(n) - Last or not found
• Average Case: O(n)

Space Complexity: O(1)

Advantages:

✓ Works on unsorted arrays

✓ Simple implementation

✓ No preprocessing needed

Disadvantages:

✗ Slow for large datasets

Binary Search:

Divide and conquer search on SORTED array

Algorithm:

int binarySearch(int arr[], int low, int high, int key) {
  while(low <= high) {
    int mid = (low + high) / 2;
    if(arr[mid] == key)
      return mid;
    else if(arr[mid] < key)
      low = mid + 1;
    else
      high = mid - 1;
  }
  return -1;
}

Time Complexity: O(log n)

Space Complexity: O(1) iterative, O(log n) recursive

Prerequisite: Array MUST be sorted

Example: Search 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72]

• mid = 16, 23 > 16 → search right
• mid = 38, 23 < 38 → search left
• mid = 23 ✓ Found!

Linear vs Binary Search:

When to use Linear:

• Small arrays (< 10 elements)
• Unsorted data
• Linked lists

When to use Binary:

• Large sorted arrays
• Frequent searches
• Read-heavy operations

Example for n = 1000:

• Linear: Up to 1000 comparisons
• Binary: Max 10 comparisons (log₂1000 ≈ 10)

Bubble Sort:

Repeatedly swap adjacent elements if in wrong order

Algorithm:

void bubbleSort(int arr[], int n) {
  for(int i=0; i<n-1; i++) {
    for(int j=0; j<n-i-1; j++) {
      if(arr[j] > arr[j+1])
        swap(&arr[j], &arr[j+1]);
    }
  }
}

Time Complexity:

• Best: O(n) - Already sorted (with optimization)
• Worst/Average: O(n²)

Space: O(1)

Stable: Yes

In-place: Yes

Working: Largest element 'bubbles up' to end each pass

Optimization: Add flag to detect no swaps (already sorted)

Selection Sort:

Find minimum element, place at beginning; repeat

Algorithm:

void selectionSort(int arr[], int n) {
  for(int i=0; i<n-1; i++) {
    int minIdx = i;
    for(int j=i+1; j<n; j++) {
      if(arr[j] < arr[minIdx])
        minIdx = j;
    }
    swap(&arr[i], &arr[minIdx]);
  }
}

Time Complexity: O(n²) always

Space: O(1)

Stable: No

In-place: Yes

Key Feature:

• Minimum swaps: O(n)
• Good when memory writes are expensive

Example: [64, 25, 12, 22, 11]

Pass 1: Min = 11, swap → [11, 25, 12, 22, 64]

Insertion Sort:

Build sorted array one element at a time

Algorithm:

void insertionSort(int arr[], int n) {
  for(int i=1; i<n; i++) {
    int key = arr[i];
    int j = i - 1;
    while(j >= 0 && arr[j] > key) {
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = key;
  }
}

Time Complexity:

• Best: O(n) - Nearly sorted
• Worst: O(n²) - Reverse sorted

Space: O(1)

Stable: Yes

In-place: Yes

Best for:

• Small arrays
• Nearly sorted arrays
• Online sorting (streaming data)

Quick Sort:

Divide & conquer using pivot element

Steps:

• 1. Choose pivot
• 2. Partition: elements < pivot go left, > pivot go right
• 3. Recursively sort left and right

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

Time Complexity:

• Best/Average: O(n log n)
• Worst: O(n²) - Already sorted

Space: O(log n) stack

Stable: No

In-place: Yes

Pivot selection:

• First/Last element
• Median of three
• Random (best)

Merge Sort:

Divide array, sort halves, merge sorted halves

Steps:

• 1. Divide array into two halves
• 2. Recursively sort each half
• 3. Merge two sorted halves

void mergeSort(int arr[], int l, int r) {
  if(l < r) {
    int m = (l + r) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);
    merge(arr, l, m, r);
  }
}

Time Complexity: O(n log n) always

Space: O(n) for merging

Stable: Yes

In-place: No

Advantages:

• Guaranteed O(n log n)
• Stable sort
• Good for linked lists
• External sorting

Heap Sort:

Build max-heap, repeatedly extract maximum

Steps:

• 1. Build max-heap from array
• 2. Swap root with last element
• 3. Heapify remaining elements
• 4. Repeat

void heapSort(int arr[], int n) {
  // Build max heap
  for(int i=n/2-1; i>=0; i--)
    heapify(arr, n, i);
  
  // Extract elements
  for(int i=n-1; i>0; i--) {
    swap(&arr[0], &arr[i]);
    heapify(arr, i, 0);
  }
}

Time Complexity: O(n log n) always

Space: O(1)

Stable: No

In-place: Yes

Key: Uses heap data structure

Counting Sort:

Count occurrences of each element

Time: O(n + k) where k = range

Space: O(k)

Use: When range is small

Radix Sort:

Sort digit by digit (LSD or MSD)

Steps:

• 1. Sort by least significant digit
• 2. Sort by next digit
• 3. Continue until most significant

Time: O(d × (n + k))

• d = digits, k = radix (base)

Space: O(n + k)

Example: [170, 45, 75, 90, 802, 24, 2, 66]

• Sort by 1s: [170, 90, 802, 2, 24, 45, 75, 66]
• Sort by 10s: [802, 2, 24, 45, 66, 170, 75, 90]
• Sort by 100s: [2, 24, 45, 66, 75, 90, 170, 802]

Both are non-comparison sorts!

Sorting Algorithms Comparison:

When to use what:

• Small array: Insertion
• Large, unsorted: Quick Sort
• Stability needed: Merge Sort
• Limited space: Heap Sort

Tree:

Non-linear hierarchical data structure with nodes connected by edges

Key Terms:

• Root: Top node (no parent)
• Parent: Node with children below
• Child: Node connected below parent
• Leaf: Node with no children
• Sibling: Nodes with same parent
• Depth: Distance from root
• Height: Longest path to leaf
• Degree: Number of children

Properties:

• N nodes → N-1 edges
• One path between any two nodes
• No cycles

Examples: File systems, HTML DOM, Organization charts

Binary Tree:

Tree where each node has at most 2 children (left and right)

Structure:

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

Types:

• 1. Full Binary Tree: Every node has 0 or 2 children
• 2. Complete Binary Tree: All levels filled except possibly last (filled left to right)
• 3. Perfect Binary Tree: All internal nodes have 2 children, all leaves at same level
• 4. Balanced Binary Tree: Height difference ≤ 1 between subtrees

Properties:

• Max nodes at level l = 2^l
• Max nodes in tree of height h = 2^(h+1) - 1
• Min height = ⌈log₂(n+1)⌉ - 1

Binary Tree Representations:

1. Array Representation:

• Root at index 0
• Left child of i: 2i + 1
• Right child of i: 2i + 2
• Parent of i: (i-1)/2

Good for: Complete binary trees

Problem: Wastes space for sparse trees

2. Linked Representation:

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

Advantages:

• Dynamic size
• No wasted space
• Easy insertion/deletion

Preferred for: General binary trees

Tree Traversal Methods:

1. Inorder (LNR):

Left → Node → Right

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

BST Result: Sorted order!

2. Preorder (NLR):

Node → Left → Right

• Used for: Copying tree, prefix expression

3. Postorder (LRN):

Left → Right → Node

• Used for: Deleting tree, postfix expression

4. Level Order (BFS):

Level by level, left to right

• Uses queue

Mnemonic: Position of N (Node) gives the name

Example Tree:

       1
      / \
     2   3
    / \
   4   5

Inorder (LNR): 4, 2, 5, 1, 3

Left-most first, then parent, then right

Preorder (NLR): 1, 2, 4, 5, 3

Root first, then left subtree, then right

Postorder (LRN): 4, 5, 2, 3, 1

Leaves first, children before parent

Level Order: 1, 2, 3, 4, 5

Top to bottom, left to right

Applications:

• Inorder: Get sorted BST elements
• Preorder: Copy/serialize tree
• Postorder: Calculate size, delete tree
• Level Order: Find level-wise info

Binary Search Tree:

Binary tree with ordering property

Property:

• Left subtree: All values < node
• Right subtree: All values > node
• Both subtrees are BSTs

Operations:

Worst case: Skewed tree (like linked list)

Key advantage:

Inorder traversal gives sorted output

Example:

       8
      / \
     3   10
    / \    \
   1   6    14

BST Operations:

Search:

Node* search(Node* root, int key) {
  if(!root || root->data == key)
    return root;
  if(key < root->data)
    return search(root->left, key);
  return search(root->right, key);
}

Insert:

• Search for position
• Insert as leaf

Delete (3 cases):

• 1. Leaf node: Simply remove
• 2. One child: Replace with child
• 3. Two children:
• Find inorder successor (smallest in right subtree)
• Replace node's data with successor
• Delete successor

Time: O(h) where h = height

AVL Tree:

Self-balancing BST where height difference between left and right subtrees ≤ 1

Balance Factor = Height(Left) - Height(Right)

• BF can be -1, 0, or 1

Why AVL?

• BST can become skewed → O(n) operations
• AVL guarantees O(log n)

Operations:

Trade-off:

• Faster search than BST
• Slower insert/delete (rotations)

Named after: Adelson-Velsky and Landis (1962)

AVL Rotations (to restore balance):

1. Left Rotation (RR case):

Imbalance due to insertion in right of right

  A            B
   \          / \
    B   →   A   C
     \
      C

2. Right Rotation (LL case):

Imbalance in left of left

      C          B
     /          / \
    B    →    A   C
   /
  A

3. Left-Right (LR case):

Left rotation on left child, then right rotation

4. Right-Left (RL case):

Right rotation on right child, then left rotation

Remember: Single rotation for LL/RR, Double for LR/RL

B-Tree:

Self-balancing search tree for disk-based storage

Properties (order m):

• 1. Root has at least 2 children (if not leaf)
• 2. Each node has at most m children
• 3. Each non-root node has at least ⌈m/2⌉ children
• 4. All leaves at same level
• 5. Non-leaf node with k children has k-1 keys

Why B-Tree?

• Reduces disk I/O operations
• Good for databases and file systems
• Stays balanced automatically

Time Complexity:

Search, Insert, Delete: O(log n)

Used in:

• Databases (indexing)
• File systems

B+ Tree:

Variation of B-Tree optimized for database indexing

Key Differences from B-Tree:

Advantages:

• All data at leaf level → consistent access time
• Leaves linked → efficient range queries
• More keys per node → shallower tree

Used in:

• MySQL InnoDB
• PostgreSQL
• File systems (NTFS, ext4)

Threaded Binary Tree:

Binary tree where NULL pointers are replaced with threads (pointers to inorder predecessor/successor)

Purpose:

• Efficient inorder traversal without recursion/stack
• Utilize wasted NULL pointers

Types:

• 1. Single Threaded: Only right NULL → successor
• 2. Double Threaded: Both NULL pointers used
• Left NULL → predecessor
• Right NULL → successor

Node Structure:

struct Node {
  int data;
  Node *left, *right;
  bool leftThread, rightThread;
};

Advantage: O(1) to find successor

Disadvantage: Complex insert/delete

Graph G = (V, E)

V = Set of vertices (nodes)

E = Set of edges (connections)

Types:

• 1. Directed (Digraph): Edges have direction
• 2. Undirected: Edges bidirectional
• 3. Weighted: Edges have values
• 4. Unweighted: All edges equal

Key Terms:

• Degree: Number of edges at vertex
• Path: Sequence of vertices via edges
• Cycle: Path that starts and ends at same vertex
• Connected: Path exists between all vertex pairs

Applications:

• Social networks (users, friendships)
• Maps (locations, routes)
• Web (pages, links)

Graph Representations:

1. Adjacency Matrix:

  0 1 2
0 [0 1 1]
1 [1 0 1]
2 [1 1 0]

• Space: O(V²)
• Edge lookup: O(1)
• Good for: Dense graphs

2. Adjacency List:

0 → 1 → 2
1 → 0 → 2
2 → 0 → 1

• Space: O(V + E)
• Edge lookup: O(degree)
• Good for: Sparse graphs

Comparison:

BFS (Breadth First Search):

Explore all neighbors before going deeper

Uses: Queue

Algorithm:

void BFS(int start) {
  Queue q;
  visited[start] = true;
  enqueue(q, start);
  
  while(!isEmpty(q)) {
    int v = dequeue(q);
    printf("%d ", v);
    for each neighbor u of v:
      if(!visited[u]) {
        visited[u] = true;
        enqueue(q, u);
      }
  }
}

Time: O(V + E)

Space: O(V)

Applications:

• Shortest path (unweighted)
• Social network (degrees of separation)
• GPS navigation
• Web crawling

DFS (Depth First Search):

Explore as deep as possible before backtracking

Uses: Stack (or Recursion)

Algorithm:

void DFS(int v) {
  visited[v] = true;
  printf("%d ", v);
  for each neighbor u of v:
    if(!visited[u])
      DFS(u);
}

Time: O(V + E)

Space: O(V) recursion stack

Applications:

• Topological sort
• Cycle detection
• Path finding
• Maze solving
• Connected components

BFS vs DFS:

• BFS: Level by level, uses queue
• DFS: Deep first, uses stack

Minimum Spanning Tree (MST):

Subset of edges that connects all vertices with minimum total weight

Properties:

• Contains V-1 edges (for V vertices)
• No cycles
• Minimum total edge weight
• May not be unique

Algorithms:

• 1. Prim's Algorithm - Vertex-based
• 2. Kruskal's Algorithm - Edge-based

Applications:

• Network design (minimum cable)
• Cluster analysis
• Approximation algorithms
• Image segmentation

Example: Connecting cities with minimum road construction cost

Prim's Algorithm:

Grow MST from a vertex

Steps:

• 1. Start with any vertex
• 2. Add minimum weight edge connecting tree to non-tree vertex
• 3. Repeat until all vertices included

Time: O(V²) or O(E log V) with heap

---

Kruskal's Algorithm:

Add edges in increasing weight order

Steps:

• 1. Sort all edges by weight
• 2. Add smallest edge if it doesn't form cycle
• 3. Use Union-Find for cycle detection
• 4. Repeat until V-1 edges

Time: O(E log E)

Comparison:

• Prim's: Better for dense graphs
• Kruskal's: Better for sparse graphs

Dijkstra's Algorithm:

Finds shortest path from source to all vertices

Requirement: No negative edge weights

Steps:

• 1. Set distance to source = 0, others = ∞
• 2. Pick unvisited vertex with minimum distance
• 3. Update distances of neighbors
• 4. Mark vertex as visited
• 5. Repeat until all visited

Time Complexity:

• Array: O(V²)
• Min-Heap: O((V+E) log V)

Applications:

• GPS navigation
• Network routing
• Social network analysis

Limitation:

• Doesn't work with negative edges
• Use Bellman-Ford for negative edges

Example Graph:

    A --(4)-- B
    |         |
   (2)       (3)
    |         |
    C --(1)-- D

Find shortest path from A:

Shortest paths from A:

• A→A: 0
• A→B: 4 (A→B)
• A→C: 2 (A→C)
• A→D: 3 (A→C→D)

Hashing:

Technique to map data to fixed-size values for fast access

Components:

• 1. Hash Function: Converts key → index
• 2. Hash Table: Array storing data
• 3. Collision Handling: When two keys map to same index

Hash Function:

h(key) = key % table_size

Time Complexity:

Good Hash Function properties:

• Uniform distribution
• Fast to compute
• Minimizes collisions

Common Hash Functions:

1. Division Method:

h(k) = k mod m

• m = table size (prime recommended)

2. Multiplication Method:

h(k) = ⌊m × (k × A mod 1)⌋

• A = constant between 0 and 1
• Often A = (√5 - 1)/2

3. Mid-Square Method:

• Square the key
• Extract middle digits as hash

4. Folding Method:

• Divide key into parts
• Add/XOR the parts

For Strings:

h(s) = (s[0] + s[1]*31 + s[2]*31² + ...) mod m

Choosing m:

• Prime number (not power of 2)
• Not close to power of 2

Collision: Two keys map to same index

Resolution Methods:

1. Chaining (Separate Chaining):

• Each slot contains linked list
• Colliding elements added to list
• Load factor can exceed 1

2. Open Addressing:

Find another empty slot

a) Linear Probing:

h(k,i) = (h(k) + i) mod m

• Problem: Clustering

b) Quadratic Probing:

h(k,i) = (h(k) + c₁i + c₂i²) mod m

• Reduces clustering

c) Double Hashing:

h(k,i) = (h₁(k) + i×h₂(k)) mod m

• Best distribution
• Two hash functions

Load Factor: α = n/m (elements/size)

Collision Resolution Comparison:

Clustering:

• Primary: Long runs of occupied slots
• Secondary: Keys with same initial probe sequence

When to use:

• Chaining: Unknown number of elements
• Open Addressing: Memory critical

Load Factor recommendations:

• Chaining: α < 1
• Open Addressing: α < 0.7
• Resize when exceeded