GATE CS 2016 Set 2 — Question 44
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.NAT+2 / -0MediumMin-Heap & Max-HeapHeapsProgramming & Data Structures
Programming & Data Structures → Heaps → Min-Heap & Max-Heap
Last updated
Question
A complete binary min-heap is made by including each integer in exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is __________.
Correct answer
8 to 8
Solution
In a min-heap, every node must be smaller than its children. Therefore, for a node with value to appear at depth , all ancestors on the path from the root to this node must have values strictly smaller than . Since the values in the heap are distinct integers starting from 1, the smallest possible values for the ancestors are . Thus, to place the value at depth , we must have at least integers smaller than . This implies:Given , the maximum possible depth is:The heap contains 1023 nodes, which corresponds to a full binary tree of depth . Since depth 8 exists in the tree, it is possible to arrange the numbers such that 9 appears at depth 8 (e.g., the path ).Thus, the maximum depth is 8.
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]