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: 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).

More Trees and Binary Search Trees questions

All Trees and Binary Search Trees questions →