in DS edited by
25,600 views
73 votes
73 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 _________.
in DS edited by
25.6k views

4 Comments

if they ask  maximum no of nodes till the level where integer 9 has been occured then answer will be 511
1
1
one thing should be remembered here while answering this question is that here depth is starting from 0, one can easily find out the max. depth which is 9(0 to 8) but the element 9 is present at the deepest level which is 8.
0
0
How about max heap for elements [1....15] and max depth at which node 3 can appear?
0
0
First derive what can be max depth of complete BT with these many nodes and then you can check easily.
0
0

5 Answers

106 votes
106 votes
Best answer

Here answer is $8$. With $1023$ nodes, we can easily build a min heap as shown in the below diagram.

Here, $9$ is pushed to the deepest possible level which is $8$ here. $(k^{th}$ smallest element in a min-heap cannot go deeper than level $k$ because the path from root to that level goes through $k-1$ smaller elements). Now, do we have enough elements to fill the right subtree to satisfy the complete binary tree property required by a heap? Yes. As shown in the diagram, up to depth $9$ (assume it is fully filled) we’ll need $2^9-1 = 511$ elements. We have $1023$ elements and so the remaining $512$ elements should go to depth $9$ which is guaranteed to have the maximum element – here $1023.$

Correct answer is $8.$

edited by

4 Comments

Total elements we need for this heap is 256, not 512.

Since we only have to fill the tree till level 7 then we can put node 9 to level 8 under node 8. we don't have to fill the 8th level as well. So to fill 7th level {$2^{h+1}$-1}+1(for node 9) = $2^{7+1}$ = 256.

3
3
The explanation is good but the diagram struck me with doubts. In the first glance it looked like a left skewed binary tree. I was like how come a left skewed binary tree become a heap in the first place as only complete or almost complete binary tree is eligible to.

After drawing the tree in paper it made sense.😁 It is a complete binary tree if we consider filling all nodes until 1023 and we can find node 9 at most level 9. Here level 1 is depth 0, thus level 9 gives depth 8. Hence the answer.
0
0
@doraemon ...it will be 7, right? as we can have a max. of 8 levels now.
0
0
59 votes
59 votes

So I have 1023 elements from 1-1023

What is the maximum depth at which element 9 can be placed?

For the purpose of working, I am considering as of now level(Root is at level 1), when we'll conclude we'll accordingly discuss about the depth.

So, suppose below is the min-heap structure(Remember here in question I have heap as a complete binary tree) under consideration I have taken for simplicity

So, as we can see, 1 will be at the root.

In this tree of 1023 node we'll have 10 levels.

Suppose I place 9 on $10^{th}$ level. Now, between 1 and this 9 on level 10, I have to fill 8 values which are larger than 1 but smaller than 9, otherwise, 9 will end up propagating up the min -heap decreasing the level at which 9 is!!

But values which are greater than 1 and less than 9 are : 2,3,4,5,6,7,8=Only 7. That means between the chain shown above in diagram, If I place 9 on level 10, then I need to fill 8 elements which are greater than 1 but less than 9, but there are only 7 of them.

So, 9 cannot come at level 10.

Now, say I place 9 at level 9, so between 1 and 9 I need to place 7 values which are greater than 1 and less than 9, and Yes I can do so with help of 2,3,4,5,6,7,8.

So, maximum level at which 9 can appear is 9!!.

Since depth is the number of edges from root to node, we see that maximum depth of 9 is 8.

Since this heap is a complete binary tree as given in the question, I won't fall short of values when I'll place 9 on level 9, because elsewhere (all the part of min-heap which is not shown above) can be filled by remaining values.

Now Another question:


What is the minimum depth at which 9 can come?

Consider below image

So root of this min-heap will be 1.

Suppose I place 9 on level 2.

Now, subtrees rooted at 1, both will contain $\frac{1023-1}{2}=511$ nodes each.

Now, subtree rooted at 9 will be min-heap and it will contain all $510$ nodes in total which are greater than 9.

Suppose I assign nodes 10-519 to sub-tree(Min-heap) rooted at 9.

Now, I have nodes remaining 2,3,4,5,6,7,8 and from 520-1023---> total 511 in the count. With these nodes, I can fill the right subtree of 1(which will also be a min-heap).

So, minimum level at which 9 can come here=2.

Hence Minimum Depth=1.

 

 

 

4 Comments

@ayush bhai you are gem :)
0
0

@Ayush Upadhyaya

511 left and 511 right total getting 1022 Bro, but the given is 1023 right where will be the one element?

0
0

root bro!

1
1
13 votes
13 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
11 votes
11 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.

4 Comments

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..
0
0
yes now clear thanks
0
0
Since the naximum distance of 9 from root is 8 so with height 8 we can have 512 nodes here the nodes should be ranging from 1 to 511....because if till height 8 we are not maintaining the nodes from 1 to 511 then its not poosible to get a min heap with those 1024 integer nodes..which is already specified in the problem that all those numbered nodes should be present in the min heap atleast and atmost once...
0
0
Answer:

Related questions