Data Structures & Algorithms

Revision Module — Let’s see if you actually understand everything.

This module is not about learning new concepts. It is about pattern recognition, exam traps, and response speed. If you can spot the trap, you save minutes on the exam.

---

1. Minimum Spanning Tree (MST) Rules#

An MST exists only in connected, undirected graphs.

Core Properties:

• Connects all vertices (V).
• Contains exactly V - 1 edges.
• Has NO cycles.
• Minimizes the total edge weight among all possible spanning trees.

The Big Two Algorithms:

1. Kruskal's: Greedy approach. Sorts edges by weight. Uses Union-Find (Disjoint Set) to avoid cycles. Great for sparse graphs.
2. Prim's: Greedy approach. Grows the tree from a single starting node using a Min-Heap (Priority Queue). Great for dense graphs.

---

2. The Heap Index Trap (0-based vs 1-based)#

Exams love to test your array mathematics for heaps. Do not memorize just one formula!

If the question specifies 1-based indexing (Root is at index 1):

• Python

  Copy

  Parent(i) = ⌊i/2⌋
  Left(i) = 2i
  Right(i) = 2i + 1
  

If the question specifies 0-based indexing (Root is at index 0):

• Python

  Copy

  Parent(i) = ⌊(i - 1) / 2⌋
  Left(i) = 2i + 1
  Right(i) = 2i + 2
  

Crucial Trap: You CANNOT compute the total "Heap Size" just by knowing the index i of a single node. An index only tells you position/geography, not how many elements actually exist in the background array!

---

3. Recurrence Matching (Instant Recognition)#

You must recognize recurrence relations instantly without applying the full Master Theorem every time:

Algorithm	Recurrence	Complexity	Why?
Binary Search	T(n) = T(n/2) + c	O(log n)	Divide search space in half (1 branch).
Merge Sort	T(n) = 2T(n/2) + O(n)	O(n log n)	Divide in half (2 branches) + linear scan to merge.
Quick Sort (Worst)	T(n) = T(n-1) + O(n)	O(n²)	Pivot is extreme, dividing array into sizes 0 and n-1.
Linear Search	T(n) = T(n-1) + c	O(n)	Check one item, recursively check the rest.

---

4. The Shortest Path Trap (BFS vs DFS)#

If a question asks for the "Shortest path in an UNWEIGHTED graph":

• BFS (Breadth-First Search): ✔️ YES! It guarantees the shortest path because it explores radially, layer by layer.
• DFS (Depth-First Search): NO! It plunges deep immediately and might find a ridiculously long, winding path first.

Mindset: "Minimum distance" + "Unweighted graph" = Brain screams BFS.

---

5. Binary Search Tree (BST) Running Times#

A BST's efficiency is entirely controlled by its height (h).

Operation	Time Complexity	Reason
Successor	O(h)	May need to walk down the tree.
Minimum	O(h)	Walk as far left as possible.
Maximum	O(h)	Walk as far right as possible.
Insert / Delete	O(h)	Walk down to the correct insertion spot.
Inorder Traversal	O(n)	Must visit every single node!

Worst Case Trap: What if the tree is completely skewed (e.g. elements inserted in sorted order)?

• Height h becomes equal to n.
• Insert, Delete, and Search drop from O(log n) to O(n).

---

6. Sorting & Searching Lightning Facts#

Time Complexity Ordering: You must know the order of complexities instantly from fastest to slowest: O(1) < O(log n) < O(n) < O(n log n) < O(n²)

Hashing vs Search:

• Hashing Avg Case: O(1) (Search time is completely independent of n). Assumes a good hash function and low collisions!
• Hashing Worst Case: O(n) (All items collide into one linked list chain).
• Binary Search: O(log n) (Requires sorted data).
• Linear Search: O(n) (Works on anything).

Quick Sort vs Randomized Quick Sort:

• What's the exact difference? Pivot selection.
• Standard Quick Sort: Deterministic (first, last, or middle).
• Randomized Quick Sort: Picks pivot completely randomly.
• Why? It heavily reduces the absolute mathematical probability of hitting the catastrophic O(n²) worst-case. The output is exactly the same, but the expected time is safely O(n log n).

---

7. Data Structure Application Match-Up#

If you see the algorithm/problem, you must instantly know the underlying Data Structure:

Algorithm / Problem	Corresponding Data Structure
BFS	Queue
DFS	Stack (Or Recursion Call Stack)
Dijkstra / Prim	Priority Queue / Min-Heap
Heap Sort	Priority Queue / Max-Heap
Secondary Storage (Hard Disk)	B-Trees (Optimized for large block reads)

---

8. Threaded Binary Trees#

Normal trees have a lot of wasted NULL pointers at the leaves. Threaded Binary Trees utilize these naturally empty pointers to point to their inorder predecessor or successor.

• Single Threaded: Points in one direction (usually towards the successor).
• Double Threaded: Points in both directions.
• Massive Advantage: Allows for O(n) Inorder Traversal WITHOUT a recursion stack! This saves memory and prevents stack overflow deeper down.

---

9. The Ecosystem View#

Data structures are not isolated islands. They form a deeply connected ecosystem. Do not memorize facts—understand the connections:

• A Priority Queue is literally just a Heap.
• Dijkstra's Algorithm is literally just BFS using a Min-Heap.
• A Stack implies DFS; A Queue implies BFS.
• Trees and Logs (O(log n)) go hand in hand because cutting things in half builds trees.

Proceed to the Practice Quiz to test your response speed against actual exam traps.