The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+35 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 (48.6k points)
edited by | 3.1k views
if they ask  maximum no of nodes till the level where integer 9 has been occured then answer will be 511

4 Answers

+45 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 (48.6k 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 

+10 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.6k 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
+7 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.8k points)
+1 vote
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 (367 points)
They are asking for  the maximum depth, at which integer 9 can be present, [1 to 1023] is not like 1,2,3,4,5,6,7.......1023 it can be random but in the range to 1 to 1023 now if we put 1,2,3,4,5,6,7,8,9 in the left subtree and then for satisfying min heap properties, we will start adding 10,11,12,13... like that in right subtree of 1,2,3,4,5.....9 . now we can count the depth which is 8 for the node nine.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,670 questions
39,280 answers
36,682 users