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.