What are common examiner traps in Linear Structures, Trees and Heaps?

Assuming linear-time queue operations by confusing a circular array implementation with a naive shifting array implementation. Swapping the full condition with the empty condition in circular queues when one slot is left empty. Assuming that melding two binary heaps takes (n log n) by naively inserting elements one-by-one, rather than using bottom-up (n) build-heap. Assuming BST melding takes (n log n) or (n2) by sequential insertion instead of the optimal in-order extract-merge-rebuild strategy taking (n). Confusing row access (X[0][i], contiguous in C) with column access (X[i][0], stride of n elements) Assuming two code segments produce different outputs without evaluating the algebraic symmetry of the initialization formula (e.g., i + j = j + i) Assuming node deletion in a singly linked list is O(1) when given a pointer to the node, forgetting that the predecessor must be found to update its next pointer. Assuming binary search can be performed in O(log n) on a sorted linked list, overlooking that random access is unavailable and traversal remains (n). Confusing the cost of a single operation with the cumulative cost across a batch of operations (e.g., n insertions giving (n2) instead of (n)). Believing that in-place pointer reversal requires O(n) extra space or takes (n2) time. Confusing the direction of singly linked list pointers (thinking FRONT points to REAR rather than REAR pointing back to FRONT in a circular list) Assuming that maintaining only FRONT is sufficient without realizing REAR is needed to insert in O(1) Assuming that having a tail pointer makes tail deletion (1), overlooking the fact that updating the predecessor's next pointer to null requires an O(n) traversal from the head in a singly linked list. Reversing the element retrieval order by confusing stack LIFO pops with queue FIFO dequeues during multi-step transfers. Off-by-one errors in repeated operation loops (e.g., repeating a sub-step k times vs k+1 times). Failing to account for the restore step when using augmented operations (e.g., needing two REVERSE calls per insertion). Underestimating loop iterations by missing that popped elements must be pushed back after the new element is inserted.

GATE CSE Linear Structures, Trees and Heaps PYQs

Standard yield8.5% of Programming and Data Structures

Across the provided GATE CS papers, this topic evaluates foundational data structures with an emphasis on implementation mechanics, boundary conditions, and asy… Read the guide

Take topic test

Questions: 14
Asked: since 2012
Total marks: 21
Marks / paper: 0.8

14 GATE CSE Linear Structures, Trees and Heaps PYQs with solutions, from Programming and Data Structures. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Linear Structures, Trees and Heaps

Concepts, patterns, formulas and traps distilled from past papers.

Across the provided GATE CS papers, this topic evaluates foundational data structures with an emphasis on implementation mechanics, boundary conditions, and asymptotic time complexities of core and advanced operations. Earlier questions focus directly on array-based circular queue pointer conditions and basic operation bounds ( $O(1)$ enqueue/dequeue). Recent questions test deep algorithmic understanding of multi-step operations like melding across disparate data structures such as doubly linked lists, binary heaps, and binary search trees.

Core concepts

Circular queue pointer management using modulo arithmetic
Empty vs full state distinction in circular array buffers
Constant-time O(1) queue operations with circular arrays
Doubly linked list concatenation via head and tail pointer updates
Bottom-up heapification (buildHeap) for array-based binary heaps
Binary search tree merging via in-order traversal and balanced tree construction
Row-major order storage of 2D arrays in C
Spatial locality and memory contiguity for row-wise vs column-wise access
Symmetric initialization functions (X[i][j] = f(i, j)) and loop invariant comparison
Singly linked list (SLL) traversal and predecessor lookup requirement for deletion
Doubly linked list (DLL) direct O(1) node deletion using bidirectional pointers
Worst-case search and insertion in sorted linked lists ( (n) per element)
In-place singly linked list reversal using O(1) auxiliary space in (n) time
Cost analysis of decrease-key in sorted lists
Circular Queue using Singly Linked List
Pointer manipulation for O(1) enqueue and dequeue
Role of FRONT and REAR pointers
Singly linked list implementation of queues
Head and tail pointer manipulation
Predecessor lookup limitation in unidirectional lists
Asymptotic time complexity analysis ( -notation) of enqueue and dequeue
LIFO (Last-In, First-Out) semantics of Stacks (Push, Pop, Top)
FIFO (First-In, First-Out) semantics of Queues (Enqueue, Dequeue, Head)
Inter-data-structure transfers and state tracking
Simulation of queue behavior using modified/augmented stack operations
Worst-case input analysis for combined stack-queue algorithms

Recurring question patterns

Circular Queue Array Implementation Mechanics
CommonMCQ2 marks2012
Given an array of size $n$ used to implement a circular queue with $(n-1)$ capacity using FRONT and REAR index pointers, identify the exact boundary condition expressions for full and empty queue states.
Queue Implementation Time Complexity
OccasionalMCQ1 marks2016
Evaluation of worst-case and amortized time complexities for basic queue operations (ENQUEUE/DEQUEUE) under circular array or linked representations.
Comparative Operation Complexity Across Data Structures
OccasionalMCQ2 marks2025
Given a specialized operation (e.g., meld/merge, split, bulk search) on multiple distinct data structures (linked lists, heaps, BSTs), determine the optimal worst-case time complexity for each structure.
Memory Layout vs Access Pattern Evaluation
CommonMCQ2 marks2015
Two or more code snippets traversing multidimensional arrays are compared with respect to computational output (e.g., symmetric values) and physical memory contiguity (row-major layout order in C).
Single vs. Doubly Linked List Operation Trade-offs
CommonMCQ1 marks2023, 2016
Evaluating the time complexity of fundamental operations (such as node deletion given a direct pointer to the target node) when comparing singly linked lists against doubly linked lists due to predecessor access.
Sequential Insertion and Maintenance in Sorted Linked Lists
CommonMCQ1 marks2020, 2016
Finding the cumulative worst-case asymptotic runtime of building or modifying a sorted linked list over multiple insertions, searches, or key updates.
Algorithmic Bounds with Space Constraints
OccasionalMCQ1 marks2022
Identifying the tight time complexity bound ( $\Theta$ -notation) for standard list manipulation algorithms (like list reversal) under strict auxiliary space constraints such as $O(1)$ space.
Pointer Invariants for Linked Implementations
RareMCQ1 marks2017
Questions describe a data structure implemented via a restricted pointer scheme (e.g., singly linked circular list with FRONT/REAR pointers) and ask which structural invariant or pointer connection enables optimal ( $O(1)$ ) standard operations.
Time Complexity of Pointer-Based Queue Implementations
OccasionalMCQ1 marks2018
A queue is defined with specific pointer configurations (e.g., head and tail pointers on a singly linked list) and fixed ends for enqueue and dequeue. Candidates must determine the tight asymptotic bounds ( $\Theta$ ) for both operations based on pointer manipulation and traversal requirements.
Interleaved Operation State Tracing
OccasionalNAT2 marks2023
A concrete sequence of elements is subjected to an explicit list of interleaved push, pop, enqueue, and dequeue operations across a stack and queue; the candidate must determine the final state (e.g., top element of the stack).
Worst-Case Loop Iteration Analysis
OccasionalNAT2 marks2016
An algorithm transferring elements between a stack and a queue based on comparison conditions is presented; the candidate must deduce the worst-case input configuration and compute the exact number of loop iterations.
ADT Simulation with Augmented Operations
OccasionalMCQ2 marks2014
Given a stack or queue equipped with a non-standard helper operation (e.g., REVERSE), the question evaluates the minimum instruction sequence needed to implement the dual data structure.

Formulas GATE uses

Circular Queue Full Condition

(\text{REAR} + 1) \bmod n == \text{FRONT}

Used when detecting a full circular queue in an array of size $n$ holding up to $n-1$ elements to prevent overlap with the empty state.

Circular Queue Empty Condition

\text{REAR} == \text{FRONT}

Used to check if a circular queue contains zero elements when both pointers initialize at the same index.

Floyd's Build-Heap Complexity

T(n) = \Theta(n)

Used to establish linear-time bottom-up heap construction when melding two array-based binary heaps.

BST Meld via In-order Merge Complexity

T(n) = \Theta(n) + \Theta(n) + \Theta(n) = \Theta(n)

Used when melding two BSTs of size $n$ by extracting sorted arrays, merging them, and rebuilding a balanced BST.

2D Row-Major Element Address Offset (0-indexed)

\text{Offset}(X[i][j]) = (i \times N + j) \times \text{sizeof}(\text{element})

Determining whether sequential loop iterations access consecutive/contiguous physical memory locations in a 2D C array of size $M \times N$ .

Cumulative Insertion into Sorted List

\sum_{k=1}^{n} (k-1) = \frac{n(n-1)}{2} = \Theta(n^2)

Used when computing the cumulative worst-case comparison/traversal cost of inserting $n$ elements into an initially empty sorted linked list.

Composite Workload Complexity

T(N) = \sum_{i} k_i(N) \cdot t_i(N)

Used when analyzing the combined worst-case time complexity of a sequence of heterogeneous operations (e.g., delete, insert, find, decrease-key) on a linked list.

Circular Linked Queue Invariant

\text{REAR} \to \text{next} = \text{FRONT}

Used to maintain a circular single linked list where enqueuing occurs after REAR and dequeuing occurs from FRONT in $O(1)$ time.

Head Insertion Time Complexity in Singly Linked List

T_{\text{insert\_head}}(n) = \Theta(1)

Used when adding a node at the head of a singly linked list using an existing head pointer.

Tail Deletion Time Complexity in Singly Linked List

T_{\text{delete\_tail}}(n) = \Theta(n)

Used when deleting the last node of a singly linked list where predecessor access requires linear traversal from the head.

Worst-Case Insertion Iterations in Stack-Queue Transfer

\sum_{k=1}^{n} (2k - 1) = n^2

Used when analyzing the maximum iterations of sorting/inserting $n$ elements from a strictly reversed queue into an ordered stack where each element requires popping and re-enqueuing preceding stack elements.

Examiner traps in Linear Structures, Trees and Heaps

Assuming linear-time queue operations by confusing a circular array implementation with a naive shifting array implementation.
Swapping the full condition with the empty condition in circular queues when one slot is left empty.
Assuming that melding two binary heaps takes (n log n) by naively inserting elements one-by-one, rather than using bottom-up (n) build-heap.
Assuming BST melding takes (n log n) or (n2) by sequential insertion instead of the optimal in-order extract-merge-rebuild strategy taking (n).
Confusing row access (X[0][i], contiguous in C) with column access (X[i][0], stride of n elements)
Assuming two code segments produce different outputs without evaluating the algebraic symmetry of the initialization formula (e.g., i + j = j + i)
Assuming node deletion in a singly linked list is O(1) when given a pointer to the node, forgetting that the predecessor must be found to update its next pointer.
Assuming binary search can be performed in O(log n) on a sorted linked list, overlooking that random access is unavailable and traversal remains (n).
Confusing the cost of a single operation with the cumulative cost across a batch of operations (e.g., n insertions giving (n2) instead of (n)).
Believing that in-place pointer reversal requires O(n) extra space or takes (n2) time.
Confusing the direction of singly linked list pointers (thinking FRONT points to REAR rather than REAR pointing back to FRONT in a circular list)
Assuming that maintaining only FRONT is sufficient without realizing REAR is needed to insert in O(1)
Assuming that having a tail pointer makes tail deletion (1), overlooking the fact that updating the predecessor's next pointer to null requires an O(n) traversal from the head in a singly linked list.
Reversing the element retrieval order by confusing stack LIFO pops with queue FIFO dequeues during multi-step transfers.
Off-by-one errors in repeated operation loops (e.g., repeating a sub-step k times vs k+1 times).
Failing to account for the restore step when using augmented operations (e.g., needing two REVERSE calls per insertion).
Underestimating loop iterations by missing that popped elements must be pushed back after the new element is inserted.

How questions are asked

Identify algebraic boundary conditions for circular buffer states
Statement selection regarding asymptotic bounds of fundamental operations
Multi-item matching / combination of worst-case time complexities for composite operations
Comparative code segment analysis with multi-statement true/false evaluation
Asymptotic comparison of SLL vs. DLL operations
Worst-case cumulative time complexity of a sequence of operations
True/False statement identification about time/space algorithmic bounds
Statement verification on pointer invariants for ADT implementation
Time complexity determination of enqueue/dequeue under a given pointer setup
Trace sequential operations and find final stack top / queue front
Count maximum while-loop iterations in a stack-queue algorithm
Identify valid instruction counts for ADT simulation

Paper trends

Shift from basic single-structure index mechanics (2012 circular queue pointer logic) and standard single-operation complexity (2016) to complex multi-structure composite operations (2025 meld requiring linear-time build-heap and in-order BST merges).
2025, 2016, 2012
Focuses on combining algorithmic loop behavior with C-specific 2D array memory mapping (row-major order and contiguous address calculation).
2015
Linked list questions in 1-mark sections have remained entirely MCQ-based, prioritizing structural differences between pointer architectures (SLL vs. DLL) and basic in-place algorithms.
2023, 2022, 2020, 2016
Shift from complex mixed-operation workloads (2016) toward cleaner, direct algorithmic/structural questions (2020, 2022, 2023).
2023, 2022, 2020, 2016
Focus is on structural and conceptual verification of pointer linkages to achieve $O(1)$ operations in queue implementations using linked lists.
2017
Testing shifts focus toward structural edge cases, such as identifying the asymmetry of tail deletion versus head insertion in a singly linked list with explicit tail pointer.
2018
Questions transitioned from conceptual ADT simulation properties (MCQ) to precise numerical state evaluations and complexity summations (NAT).
2023, 2016, 2014
Consistent 2-mark weightage when stacks and queues are tested in combination rather than in isolation.
2023, 2016, 2014

Difficulty notes

Easy questions test direct definitions and standard index arithmetic (e.g., circular queue pointer expressions or standard $O(1)$ bounds). Medium questions require synthesizing optimal multi-step algorithms (e.g., melding two BSTs or Heaps) to derive tight asymptotic worst-case bounds $(\Theta(n))$ .