number of comparision in searching in BST

Question

Consider the following Binary Search Tree

               10
             /    \
            5      20
           /      /  \           
          4     15    30
               /  
              11      

If we randomly search one of the keys present in above BST, what would be the expected number of comparisons?

(A) 2.75
(B) 2.25
(C) 2.57
(D) 3.25

Answer 1

Expected number of comparisons will be the sum of the product of probability of an item being the searched value and the no. of comparisons for the same. We are given that search key is chosen randomly from one of the keys present in the tree. So, the probability for each item being the searched key = $\frac{1}{n}$, where $n$ is the total no. of keys in the tree. 

In a BST, if an item matches at level $h$, we would have done $h$ comparisons. 

So, $\text{Expected no. of comparisons} = \sum_{i = 1}^n h_i \times \frac{1}{n} \\ \text{where }h_i \text{ is the level of node }i \\ =\sum_{i=1}^7 h_i \times \frac{1}{7} \\ = \frac{1}{7} + \frac{2}{7} + \frac{2}{7} + \frac{3}{7} + \frac{3}{7} + \frac{3}{7} + \frac{4}{7} \\ = \frac{18}{7} = 2.57$.

Comments

@Arjun sir, what if the number to be searched is not from the nodes present in BST? Do we account for unsuccessful try wherein we check whether there are left or right children?

---

If we say number of comparisons, then if element does not equals node’s key then again one more comparison required to check if it is larger than node or lesser than node? Based on which we go either left or right of tree, Am I right?

---

it is mention in the question that we have to search one of they keys present in the given BST

Answer 2

Answer (C)

Expected number of comparisons will be average comparisons, as element to be  searched is in the list( it is already given ) so

For level 0  node we will require 1 comparison------------→total comparisons at level 0  $1*1=1$

For a single level 1  node we will require 2 comparison.--->total comparisons at level 1 $2*2=4$

For a single level 2  node we will require 3 comparison----->total comparisons at level 2 $3*3=9$

For a single level 2  node we will require 3 comparison----->total comparisons at level 3 $4*1=4$

total comparisons $= 1 + 4 + 9 + 4=18$

 

average comparisons $= 18/7 = 2.57$

Option (C)