Complete binary tree

Question

If I have a complete binary tree and I need to find the average number of comparison to find any random key. Can I use this strategy like :-

We can keep track of number of nodes per level and apply:-

Summation (Level * number of nodes at that level) / total number of nodes.

Here summation is Sigma.

And here I will consider level of root = 0 or 1 ?

Well defaUlt we tAke as 0 but still...

Answer 1

https://gateoverflow.in/16124/isro2014-28

Comments

Ok sir i got it.Some Doubts though :-

1. Is the above formula applicable only for binary search tree ?

2. The Question given in your solution talks about binary search then how did they get the idea that ok lets construct a binary search tree and apply this formula ?

---

Sir Please Kindly Reply

---

sorry
i have no basic idea about this topic

---

can i solve this by this method

Average time complexity of binary search algorithm is log₂N.

here N=11, so ans = log₂ 11 = 3.46