The GATE Grind

GATE 2025 CS (CS2) – Question 38

Programming and Data Structures · Trees and Binary Search Trees · 2 marks · Multiple choice

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?

  1. P: $\Theta(1)$, Q: $\Theta(n)$, R: $\Theta(n)$
  2. P: $\Theta(1)$, Q: $\Theta(n\log n)$, R: $\Theta(n)$
  3. P: $\Theta(n)$, Q: $\Theta(n\log n)$, R: $\Theta(n^2)$
  4. P: $\Theta(1)$, Q: $\Theta(n)$, R: $\Theta(n\log n)$

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: link the tail of one list to the head of the other in $\Theta(1)$. Q: concatenate the arrays and run build-heap in $\Theta(n)$. R: merge the two inorder sequences and rebuild a BST in $\Theta(n)$.