binary heap

Question

Consider a binary min heap containing n elements and every node is having degree 2 ( i.e. full binary min heap tree). What is the probability of finding the largest element at the last level ?

According to my understanding the largest element has to be a leaf and since leafs can be on two levels last and second last therefore the probability should be 1/2

Comments

I have read all comments and you need to understand difference between full tree and complete tree. Question has given full tree you search on google about full tree. Answer is 1. And they have asked about level and not left or right subtree. So maximum is always at last level.

---

https://en.wikipedia.org/wiki/Binary_tree

---

@pankaj...since max can be present in last two levels, we can say that,

P(last level)+P(second last level)=1,

but how you are concluding that P(last level)=P(second last level) and hence P(last level)=1/2...

it will depend on nos of leaves present in last level and second last level...

Answer 1

By Constructing a min Heap , we can say that the maximum element can be any where in the last level.
There is not any possibility that any internal node contains the maximum element.
So probability of getting maximum element at leaf level is 1.

Comments

Also, key values should be unique.

Answer 2

there is ambigutiy...

if leaf is in 2 levels than p=0.5 and if it is in last level p=1...that depends on value of n.