GATE CSE
First time here? Checkout the FAQ!
x
+11 votes
1.9k views
A complete binary min-heap is made by including each integer in $[1, 1023]$ 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 _________.
asked in DS by Veteran (41.9k points)  
edited by | 1.9k views
if they ask  maximum no of nodes till the level where integer 9 has been occured then answer will be 511

4 Answers

+24 votes
Best answer

Here answer is 8. With 1024 nodes, we can easily build min heap Check following diagram

Now once we place 1-9 then remaining elements can be placed easily to fill up heap (While keeping heap property of course) Total elements we need for this heap is 512, we have given 1024 ! So Yes, 8 is answer !

answered by Veteran (41.9k points)  
edited by

yes ...heap should be a complete binary tree and here also it is  a complete BT. Because we have total 1024 elements and with height(or depth) = 9 we can have total (2(9+1) - 1) = 1023 element in complete BT.

Actually we need 511 elements for this heap. The max. depth possible is 8, so max. nodes that can be present in a complete binary tree of depth 8 = 511.

But since we have 1023 elements, we could achieve a complete binary min. heap of depth 9, which would cover all 1023 elements. But, the max. depth of node 9 can only be 8. Actually max. depth of node 10 can be 9 but that is not asked here.
The kth smallest element cannot be deeper than the kth level of the heap, since the path from it to the root must go through elements of decreasing value. (root is at level 1)

9 is 9th smallest.
So, 9 can be at level 9 i.e. at depth 8.

Why 511 elements are required? element 9 is present at a depth of 8, but in a heap it is not necessary that depth 8 should be completely filled. SO, all depths upto 7 should be filled and it requies 2(7+1) -1 elements upto depth 7 and 1 element 9.

+8 votes
Add 1,2,3,4,5,6,7,8,9 in left skewed fashion. Remaining elements can be added accordingly. So, 9 will be present at depth 8.
answered by Active (1.5k points)  
Answer is correct , explanation is wrong.
I am getting 3. Because it's complete min binary heap. I don't know how they are getting 8.
Navin , check my answer, you'll know !
how the ans is 8 ?pls explain? yes it will be 8 if the tree is not complete ?if it is complete then each parent node will have left child and right child.Then how the tree will look like?

 babai  in image akash just put imagination of tree .. in his ans right of root node i.e. 1 there are 255 nodes in arragment which satisfies the given condition... like then right of node 2 there are 127 nodes... like this tree will be look like...

yess but i can't understand how 255 nodes are there in the right of root node and this satisfying this condition  pls explain this Anirudh once this clear rest will be easy.
check with 8 nodes ,, put 1,2,3 on left side rest full with property of min heap.( root should be less than left or right child , their is no comparision between left and right child)

he done right on top of his explaination...try to do for 16 nodes.

you get idea..
yes now clear thanks
+4 votes
In minheap

ParentNode <= ChildNode

So if ChildNode = 9 then parent can be from [1,8]...choose 8 since we max depth

So if ChildNode = 8 then parent can be from [1,7]...choose 7 since we max depth

...

...

So if ChildNode = 2 then parent will be 1

so total depth will be 8
answered by Active (1.7k points)  
0 votes
With 1023 elements the min height of a tree can be = floor(log1023) i.e 9.

here Depth and height have direct correlation max depth possible=max height

we can construct a tree such that all integers below 9 fall on one side and can preserve max-heap property as well.

now how many elements which are less than 9 are there so that you can construct such tree?

Integers less than 9 are 8. so at every level we use one integer to place 9 as far as possible from root so that we can get max depth.

so 8 such integers are there hence answer is 8.

Had they given something like this [0,1023] then max depth =9.

I know this answer requires lot of intuition , im sorry if this is not clear.
answered by (91 points)  


Top Users Jul 2017
  1. Bikram

    4062 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1850 Points

  4. joshi_nitish

    1658 Points

  5. Arjun

    1294 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1112 Points

  8. Shubhanshu

    1054 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    706 Points


24,022 questions
30,966 answers
70,346 comments
29,342 users