The Core of the Algorithm Paper
In the GATE Computer Science syllabus, Data Structures & Algorithms (DSA) carries the highest weightage (often 12-15 marks). While arrays, stacks, and queues are foundational, the examiners reserve the toughest, highest-scoring questions for Non-Linear Data Structures: Trees and Graphs.
Questions on these topics are highly conceptual. They rarely ask for pure code; instead, they give you a sequence of operations and ask for the resulting structure, or they ask for theoretical bounds (time complexities).
Pillar 1: Trees
A tree is an acyclic, connected graph. The most critical sub-type for GATE is the Binary Tree.
Binary Trees & Their Properties
- Maximum nodes at level l = 2^l (assuming root is level 0).
- Maximum nodes in a tree of height h = 2^(h+1) - 1.
- In a strictly binary tree (every node has 0 or 2 children), if there are 'n' leaf nodes, there are 'n-1' internal nodes with two children. (Frequently tested!)
Binary Search Trees (BST)
To master BSTs, know the property: Left Child < Parent < Right Child.
- Traversals:
- Inorder: Left, Root, Right. Crucial Rule: Inorder traversal of a BST always yields elements in sorted (ascending) order.
- Preorder: Root, Left, Right.
- Postorder: Left, Right, Root.
- GATE Trick: If you are given the Preorder traversal of a BST, you actually have two traversals (since you know Inorder is just the sorted Preorder). With any two traversals (one must be Inorder), you can uniquely construct the exact tree diagram.
AVL Trees (Height-Balanced BSTs)
BSTs suffer from poor worst-case performance O(n) if they become skewed. AVL trees fix this by maintaining a balance factor: -1, 0, or 1.
- Balance Factor = Height of Left Subtree - Height of Right Subtree.
- Rotations: You must be able to visually trace rotations when an insertion unbalances the tree.
- LL Imbalance: Right Rotation.
- RR Imbalance: Left Rotation.
- LR Imbalance: Left Rotation then Right Rotation (Double rotation).
- RL Imbalance: Right Rotation then Left Rotation (Double rotation).
- GATE Question Type: "Insert sequence [10, 20, 30, 40, 50] into an empty AVL tree. What is the root at the end?"
Heaps
A complete binary tree that satisfies the heap property.
- Max-Heap: Parent >= Children.
- Min-Heap: Parent <= Children.
- Used primarily for Priority Queues.
- Time Complexities: Insertion: O(log n). Extract Max/Min: O(log n). Heapify (building a heap from an unsorted array): O(n) — Not O(n log n) as commonly mistaken.
Pillar 2: Graphs
Graphs represent arbitrary relationships. A graph G = (V, E) where V is vertices, E is edges.
Graph Representation
- Adjacency Matrix: V x V matrix. Space = O(V²). Best for dense graphs or answering "Is there an edge between u and v?" in O(1) time.
- Adjacency List: Array of linked lists. Space = O(V + E). Best for sparse graphs and for most algorithms (BFS/DFS).
Graph Traversals (The Core GATE Topics)
1. Breadth-First Search (BFS): Traverses level-by-level starting from a source.
- Uses a Queue.
- Solves the Shortest Path problem on unweighted graphs.
- Time Complexity: O(V + E) using adjacency list.
2. Depth-First Search (DFS): Explores as deep as possible before backtracking.
- Uses a Stack (usually implemented via recursion).
- Used for detecting cycles, topological sorting, and finding strongly connected components.
- GATE Metric: Keep track of Discovery Time and Finish Time for nodes. It helps in classifying edges (Tree, Back, Forward, Cross edges). A graph has a cycle if and only if DFS yields a "Back Edge".
Minimum Spanning Trees (MST)
For a connected, weighted, undirected graph, an MST connects all vertices with minimum total edge weight without forming cycles. (Edges = V - 1).
Kruskal’s Algorithm:
- Greedy approach. Sort all edges by weight. Pick the smallest edge. Add it to MST if it doesn't form a cycle.
- Uses Disjoint Set (Union-Find) data structure.
- Time Complexity: O(E log E).
Prim’s Algorithm:
- Starts from an arbitrary node. Maintains a set of nodes included in MST. Always picks the minimum weight edge that connects an included node to a non-included node.
- Very similar to Dijkstra's algorithm.
- Time Complexity: O(E log V) using a Min-Heap.
Shortest Path Algorithms
- Dijkstra's Algorithm: Single-source shortest path. Fails if there are negative weight edges. Time: O(E + V log V) with Fibonacci heap.
- Bellman-Ford Algorithm: Single-source shortest path. Works with negative weight edges. Detects negative weight cycles. Time: O(V * E).
- Floyd-Warshall Algorithm: All-pairs shortest path. Dynamic programming approach. Time: O(V³).
Strategy for Preparation
Graph and Tree questions in GATE are not about writing code; they are about manual execution. When preparing, take a complicated graph and manually trace the state of the Queue in BFS or the Distance Array in Dijkstra step-by-step. If you can confidently dry-run these algorithms on paper, you will not lose marks in the exam.