GATE 2025 CS (CS2) – Question 38
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) P: $\Theta(1)$, Q: $\Theta(n)$, R: $\Theta(n)$
Explanation
**P: unsorted doubly linked list with head and tail pointers.** Make the tail of one list point to the head of the other: $\Theta(1)$.
**Q: min-heap stored in an array.** Concatenate the two arrays (copy of size $\Theta(n)$) and run **build-heap**, which takes $\Theta(n)$. So $\Theta(n)$.
**R: binary search tree.** Do an inorder traversal of both trees to get two sorted sequences ($\Theta(n)$), merge them ($\Theta(n)$), and rebuild a balanced BST from the sorted array ($\Theta(n)$). So $\Theta(n)$.
Answer: P $\Theta(1)$, Q $\Theta(n)$, R $\Theta(n)$: option (A).