GATE CS 2025 Set 2 — Question 38
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+2 / -0.67MediumDoubly Linked ListsLinked ListsProgramming & Data StructuresMin-Heap & Max-HeapHeapsBinary Search TreesTrees
Programming & Data Structures → Heaps → Binary Search Trees
Last updated
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 of these data structures?
Correct answer
(A) P: Θ(1), Q: Θ(n), R: Θ(n)
Solution
1.P (Unsorted doubly linked list): Since the list maintains pointers to both the head and the tail, melding two lists involves simply updating the
next pointer of the first list's tail to point to the second list's head and updating the prev pointer of the second list's head. This is a constant time operation, .2.Q (Min-heap implemented using an array): To meld two binary heaps stored as arrays, the standard efficient approach is to concatenate the elements of both arrays (size ) and then perform the
buildHeap operation (heapify). Concatenation takes and buildHeap takes linear time . Thus, the total complexity is .3.R (Binary Search Tree): To meld two BSTs efficiently, one can perform an inorder traversal on both trees to produce two sorted lists (), merge the two sorted lists into one (), and then build a new balanced BST from the sorted list (). The total worst-case complexity is .
Therefore, the complexities are P: , Q: , R: .Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Heaps
2026 Set 2 Q12The set T represents various traversals over binary tree. The set S represents the order of…2026 Set 2 Q19Consider the following three ANSI-C programs, P1, P2, and P3. P1 [code] P2 [code] **P3**…2026 Set 1 Q23Let be an odd number greater than 100. Consider a binary minheap with elements stored in an…2026 Set 1 Q24Consider a hash table that is initially empty. The hash table is maintained…2026 Set 1 Q27Consider the following C statements: Which of the following options is/are correct? [figure]