Let f(n) be the average number of full nodes in an n-node binary search tree.
a. determine the values of f(0) and f(1).
b. show that for n > 1
f(n)=n−2 /n +1/ n (sum n−1 i=0(f(i)+f(n−i−1)) start at i = 0 end at n-1 for the summation
c. show (by induction) that f(n)=(n−2)/3 is a solution to the equation in part (b), with the initial conditions in part (a).
d. use the results of exercise 4.6 to determine the average number of leaves in an n-node binary search tree.

Function name: poly parameters: int returns: int description: a polynomial of degree n with coefficients a0,a1,a2,a3, . . ,an is the function p(x) = a0+a1x+a2x2+a3 ∗ x3+ . . +an ∗ xn this function can be evaluated at different values of x. for example, if: p(x) = 1+2x+ x2, then p(2) = 1+2 ∗ 2+22 = 9. if p(x) = 1+x2+x4, then p(2) = 21 and p(3) = 91. write a function poly() that takes as input a list of coefficients a0, a1, a2, a3, . . , an of a polynomial p(x) and a value x. the function will return poly(x), which is the value of the polynomial when evaluated at x.