GATE CSE 2016 Set 2 | Question: 34

Question

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 _________.

Comments

if they ask  maximum no of nodes till the level where integer 9 has been occured then answer will be 511

---

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.

---

How about max heap for elements [1....15] and max depth at which node 3 can appear?

---

First derive what can be max depth of complete BT with these many nodes and then you can check easily.

Answer 1

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.$

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.

---

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.

---

@doraemon ...it will be 7, right? as we can have a max. of 8 levels now.

Answer 2

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.

 

 

 

Comments

good explanation

---

thanks

---

Very nice explanation @Ayush Upadhyaya

just small doubt

if values range is greater >1023 then also value for both max and min depth will remains same right

in case of MAX ..in MIN heap kth largest element cant be deeper than level k

and in case of MIN ..we place 9 at 2nd level only and if we take #nodes > 1023 only last level may be partially filled so no prob ..m i right ?

---

@jatin -khachane 1-I didn't get you jatin.See, what you can do is for better understanding, take a small example of some values like 1,2,3,....16.Make a min-heap or max heap whatever you want and see what you are able to observe in it.

Anyways let me know what you were asking for. :)

---

:)

Actually in question it is given A complete binary min-heap is made by including each integer in [1,1023] exactly once ..if # of values in min heap > 1023 m considering that case

in that case height will be greater then 9 but still value "9" still be possible at max depth 8 and MIN depth 2

is this right ?? dnt know if m able to put my doubt properly

---

Yes surely 9 cannot go beyond level 9, otherwise what values will you fill in between 1 and 9 in case of min heap?

And for minimum depth you have to take care that when once, you have placed your desired element, at the minimum place then there should not be case that you are not able to form min heap with remaining elements.

For these type of problems I take a small example on say 16 values, do some work and apply the observation to this big example.And it works.

---

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).

@Ayush Upadhyaya Sir how can you say with surity that these elements will always form a min heap?

---

@Sambhrant MauryaYou can form a min-heap with those elements.

---

@Ayush Upadhyaya So then any random collection of elements will always form a heap?

---

just put all these elements in the increasing order in array representation you will be able to form a min heap from that , this is the best explaination for this ans

---

Super explaination sir .
Step by step .

---

@ayush bhai you are gem :)

---

@Ayush Upadhyaya

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

---

Satyajitdas

root bro!

Answer 3

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

Answer 4

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.

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..

---

yes now clear thanks

---

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...