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

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.

Comments

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.