Skip to content
GATEiit

GATE CSE 2025 Session 2 Q38: Worst-case meld time for list, array heap and BST

Question

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 nn of these data structures?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2025 final answer key)

Concept used: Splice lists by pointers; rebuild a heap bottom-up in linear time; merge two BSTs through their sorted in-order sequences.

First step: Concatenate the two heap arrays and run build-heap; for BSTs, merge the two in-order lists and build a balanced tree from the sorted result.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 2 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

More Programming and Data Structures PYQs

PracticePractise Programming and Data Structures questions →Full paperAll GATE CSE 2025 Session 2 questions →