Back to Study Material GATE Exam

Data Structures and Algorithms

Data Structures and Algorithms (DSA) is the highest-weightage topic in the GATE CS exam, contributing between 12 and 18 marks across most recent papers. Th...

Data Structures and Algorithms

Core Data Structures Tested in GATE CS

Data Structures and Algorithms (DSA) is the highest-weightage topic in the GATE CS exam, contributing between 12 and 18 marks across most recent papers. This makes it the single most important area to master. The key data structures tested are arrays, linked lists, stacks, queues, trees (binary trees, BSTs, AVL trees, B-trees), heaps, and graphs. Each structure has associated operations whose time and space complexity you must know precisely.

Arrays provide O(1) random access but O(n) insertion and deletion at arbitrary positions due to shifting. Two-dimensional arrays stored in row-major order have the element at position [i][j] located at base + (i times number_of_columns + j) times element_size. GATE frequently tests memory address calculations for 2D arrays.

Linked lists support O(1) insertion and deletion at the head but O(n) access by index. A singly linked list requires one pointer per node; a doubly linked list requires two. Common operations tested include reversing a linked list in-place, detecting a cycle using Floyd's algorithm (two pointers advancing at different speeds), and merging two sorted linked lists.

Stacks operate on last-in first-out (LIFO) semantics. They are used in function call management (the call stack), expression evaluation (infix to postfix conversion), and backtracking algorithms. A GATE classic: converting the infix expression (A + B) * (C - D) to postfix gives A B + C D - *. The algorithm uses a stack to hold operators and applies precedence rules to decide when to pop.

Queues operate on first-in first-out (FIFO) semantics. A circular queue of capacity n can hold at most n-1 elements when implemented with front and rear pointers (to distinguish full from empty). A double-ended queue (deque) supports insertion and deletion at both ends.

Priority queues are typically implemented as binary heaps. A min-heap supports extract-min in O(log n) and insert in O(log n). Building a heap from an array of n elements takes O(n) time using the bottom-up heapification process, which is better than the naive O(n log n) approach of inserting elements one by one.

Graphs can be represented as adjacency matrices (O(V squared) space, O(1) edge query) or adjacency lists (O(V + E) space, O(degree) edge query). The choice of representation affects the time complexity of algorithms running on the graph.

Trees and Heaps: Concepts and GATE Patterns

Binary trees are among the most frequently tested data structures in GATE. A binary tree has at most two children per node. A full binary tree has every internal node with exactly two children. A complete binary tree has all levels filled except possibly the last, which is filled from left to right. A perfect binary tree has all levels completely filled. These definitions are tested directly in GATE questions that ask you to count nodes or determine the height.

A binary search tree (BST) maintains the invariant that every node in the left subtree has a smaller key and every node in the right subtree has a larger key. Inorder traversal of a BST produces keys in sorted order. GATE questions often ask for the number of distinct BSTs that can be formed from n distinct keys, which equals the nth Catalan number: C(n) = (2n choose n) divided by (n+1).

AVL trees are self-balancing BSTs where the height difference between the left and right subtrees of any node is at most 1. When an insertion or deletion violates this property, rotations are performed. The four rotation cases are LL (single right rotation), RR (single left rotation), LR (left rotation followed by right rotation), and RL (right rotation followed by left rotation). The height of an AVL tree with n nodes is O(log n), guaranteeing O(log n) search, insertion, and deletion.

B-trees are balanced multi-way search trees used in database indexing. A B-tree of order m has at most m children per node and at least the ceiling of m/2 children per internal node. All leaf nodes are at the same depth. GATE questions on B-trees often ask you to determine the minimum and maximum number of keys that can be stored in a B-tree of given order and height.

Heaps are complete binary trees stored efficiently in arrays. For a node at index i (1-indexed), the parent is at index i/2 (integer division), the left child is at 2i, and the right child is at 2i+1. A max-heap has every parent greater than or equal to its children. Heap sort uses a max-heap to sort an array in O(n log n) time and O(1) auxiliary space, making it an in-place sorting algorithm.

The key operations on heaps for GATE are heapify (fix one violation in O(log n)), build-heap (create a heap from an unsorted array in O(n)), extract-max or extract-min (remove the root in O(log n)), and increase-key or decrease-key (update a key and restore the heap property in O(log n)).

Graph Algorithms and Hash Tables

Graph algorithms constitute a significant portion of GATE DSA questions. Breadth-first search (BFS) explores nodes level by level using a queue and runs in O(V + E) time. Depth-first search (DFS) explores as deep as possible before backtracking, using either a stack or recursion, and also runs in O(V + E) time. DFS is used for topological sorting, cycle detection, and finding strongly connected components.

Topological sorting applies to directed acyclic graphs (DAGs) and produces a linear ordering of vertices such that for every directed edge from u to v, u comes before v. It can be computed using DFS (output nodes in reverse finish order) or using Kahn's algorithm (repeatedly remove nodes with in-degree zero). GATE may ask whether a graph has a topological ordering (equivalent to asking whether the graph is a DAG) or may ask you to produce the lexicographically smallest topological sort.

Dijkstra's algorithm finds single-source shortest paths in graphs with non-negative edge weights. Using a binary heap as the priority queue, it runs in O((V + E) log V) time. Bellman-Ford handles negative edge weights and detects negative cycles, running in O(VE) time. Floyd-Warshall finds all-pairs shortest paths in O(V cubed) time.

Minimum spanning trees (MSTs) are computed by Prim's algorithm (grows the MST greedily from a source vertex) or Kruskal's algorithm (sorts edges by weight and adds them if they do not form a cycle, using a Union-Find data structure). Both run in O(E log V) time. GATE questions often give a weighted graph and ask for the total weight of the MST or for the order in which edges are added.

Hash tables provide O(1) average-case insertion, deletion, and lookup. Collisions are handled by chaining (each bucket holds a linked list of elements) or open addressing (probe for the next empty slot). Common probing strategies are linear probing, quadratic probing, and double hashing. GATE tests the load factor (number of elements divided by number of buckets) and its effect on performance, as well as the number of collisions for specific hash functions and input sets.

For competitive scoring in GATE DSA, practise computing the number of comparisons made by sorting algorithms on specific inputs, tracing BFS and DFS on given graphs, and computing shortest paths step by step. These are reliable sources of 2-mark questions.