First time here? Checkout the FAQ!
+17 votes
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 (44k points)  
edited by | 2.2k views
if they ask  maximum no of nodes till the level where integer 9 has been occured then answer will be 511

4 Answers

+26 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 (44k 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.

@daddy the question says COMPLETE BINARY MIN HEAP  so how have you made the heap??? it is not the diagram of complete binary min heap 

+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 (101 points)  

Top Users Sep 2017
  1. Habibkhan

    7808 Points

  2. Warrior

    2746 Points

  3. rishu_darkshadow

    2692 Points

  4. Arjun

    2672 Points

  5. A_i_$_h

    2426 Points

  6. nikunj

    1980 Points

  7. manu00x

    1920 Points

  8. Bikram

    1854 Points

  9. makhdoom ghaya

    1770 Points

  10. SiddharthMahapatra

    1718 Points

26,239 questions
33,805 answers
31,159 users