Consider the following binary search treeAny random element from the given Binary Search Tree is to be searched using thestandard algorithm. In the Binary Search Tree above(i) Determine the average or expected number of comparisons required to locate theelement.(ii) Determine the number of comparisons in the worst case.a. 2.89 and 3b. 2 and 4c. 2.89 and 4d. 3 and 4e. 2.8 and 3.5

Binary search tree is a data structure that allows to maintain a sorted list of numbers.Binary Search Tree is a node-based binary tree data structure.It has the following properties:The left subtree of a node contains only nodes with keys lesser than the node’s key.The right subtree of a node contains only nodes with keys greater than the node’s key.The left and right subtree each must also be a binary search tree.Answer is Option CThe formula for calculating the average or expected no. of comparisons required to locate any random element No. of levels = nNo. of elements in level n = LnTotal no. of elements = Lt = L1 +L2 +L3 …. +LnAverage no. of comparisons = (1*L1 + 2*L2 + 3*L3 + …. + n*Ln) / LtGiven in questionn=4L1 =1, L2 =2, L3 =3, L4 = 3, Lt =9Average no. of comparisons = (1*1 + 2*2 + 3*3 + 4*3) / 9 = (1+4+9+12)/9 = 26/9 = 2.89If the tree has a height h, the maximum no. of comparisons is h+1, which happens if one comparison per level done.In question, h=3Maximum no. of comparisons = h+1 = 3+1 = 4(i) Average no. of comparisons = 2.89(ii) Maximum no. of comparisons = 4

Answered: Consider the following binary search…