GATE CS 2025 Set 2 Q.38: Arrays and Linked Lists

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:

P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.

Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size $n$ of these data structures?

P: $\Theta(1)$ , Q: $\Theta(n)$ , R: $\Theta(n)$

P: $\Theta(1)$ , Q: $\Theta(n \log n)$ , R: $\Theta(n)$

P: $\Theta(n)$ , Q: $\Theta(n \log n)$ , R: $\Theta(n^2)$

P: $\Theta(1)$ , Q: $\Theta(n)$ , R: $\Theta(n \log n)$

Official answer and solution

Official answer: A
From: Official GATE 2025 answer key

Solution

Find the optimal worst-case algorithm for concatenating two doubly linked lists (P), building a heap from two arrays of size $n$ (Q), and merging two BSTs via sorted arrays (R).

P (Unsorted doubly linked list with head and tail pointers): We link the tail of the first list to the head of the second list and update the combined tail pointer in $\Theta(1)$ time.
Q (Array-based Min-Heap): We copy the two arrays of size $n$ into a single array of size $2n$ in $\Theta(n)$ time and run Floyd's bottom-up Build-Heap in $\Theta(n)$ worst-case time.
R (Binary Search Tree): We perform an inorder traversal of each BST to produce two sorted arrays of size $n$ in $\Theta(n)$ time, merge the two sorted arrays into a sorted array of size $2n$ in $\Theta(n)$ time, and recursively construct a balanced BST from the sorted array in $\Theta(n)$ time.

Final answer

Option (A)

Common trap

Assuming merging two BSTs requires inserting $n$ elements one by one in $\Theta(n \log n)$ time.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 38 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source