Data Structures for the GATE Exam

Common failure modes

These are the patterns that cause most candidates to lose marks on this topic. Recognising them in advance is half the work.

• !Confusing in-order, pre-order, and post-order traversal results — especially for non-binary trees
• !Miscounting levels in a complete binary tree (0-indexed vs 1-indexed root)
• !Misidentifying AVL rotation type (LL, LR, RL, RR) when the insertion path has a bend
• !Forgetting that hash-table operations are O(1) amortised, not O(1) worst case
• !Mixing up adjacency-matrix and adjacency-list space complexity for sparse vs dense graphs

Study tips

• 1Trace every tree operation (insertion, deletion, rotations) by hand on small examples before attempting GATE questions.
• 2Memorise heap property maintenance: after insertion (sift-up) and after deletion of max/min (sift-down).
• 3For graphs, know both BFS and DFS iterative implementations (using explicit stack/queue) — GATE sometimes asks about the algorithm without specifying recursion.
• 4Drill BST operations with exact comparisons so you can build a BST from a given sequence in under 30 seconds.
• 5Practice deriving adjacency-list and adjacency-matrix space for both directed and undirected graphs.

Sample GATE Data Structures questions

These sample items mirror the format and difficulty of real GATE questions. Practice with thousands more on the free Koydo question bank.

1. 1

   The in-order traversal of a binary search tree gives elements in:

   • ADescending order
   • BAscending orderCorrect
   • CLevel order
   • DInsertion order
   Why this answer?

   (GATE CS style) By the BST property, the left subtree contains smaller keys and the right subtree contains larger keys. In-order traversal visits left → root → right, which yields keys in ascending sorted order.

2. 2

   What is the maximum number of nodes in a binary tree of height h (where height of a single node is 0)?

   • Ah
   • B2h
   • C2^(h+1) − 1Correct
   • Dh²
   Why this answer?

   (GATE CS style) A full binary tree of height h has nodes at levels 0, 1, …, h. The maximum total is 1 + 2 + 4 + … + 2^h = 2^(h+1) − 1.

3. 3

   In a max-heap, the minimum element can be located in:

   • AThe root only
   • BAny leaf nodeCorrect
   • CThe last internal node
   • DThe left-most node
   Why this answer?

   (GATE CS style) In a max-heap the maximum is always at the root. The minimum element has no heap-order constraint on its position other than that it must be a leaf (since every non-leaf is greater than at least one child).

4. 4

   For a graph with V vertices and E edges, an adjacency list representation uses space proportional to:

   • AO(V²)
   • BO(E)
   • CO(V + E)Correct
   • DO(V log V)
   Why this answer?

   (GATE CS style) An adjacency list stores one list entry per vertex (O(V) total list headers) and one entry per directed edge (O(E) total edge entries), giving O(V + E) overall.