Answer required in written form with all steps performed.

Q4. Let Key, Keyz, ...., Key, be the n keys in order and let p; be the probability that Key, is the search key. If c is the number of comparisons needed to find Key, in a given tree, the average search time for that tree is: Ecipi, where i= 1 ton An optimal tree has the minimum value from the above summation. Following are three different trees when n=3, pl = 0.7, p2 = 0.2 and p3 = 0.1 Which tree is optimal? ( Key 3 Key 1 Key 1 Key 2 3 3 Key 2 Key 1 Key 2 3 1 2 2 3