410 Let f N be the average number of full nodes in an Nnode

4.10 Let f (N) be the average number of full nodes in an N-node binary search tree. Determine the values of f(0) and f(1). Show that for N > 1 f(N)=N2N+1Ni=0N1(f(i)+f(Ni1)) 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). Use the results of Exercise 4.6 to determine the average number of leaves in an N-node binary search tree.

Solution

(i) is trivially 0 both times, because you need three nodes minimum to have a full node. (one parent plus two children). So f(1) = f(2) = 0. Not asked, but needed below, f(0) = 0 is also trivial.

(ii) I\'ll rewrite that as (N-2)/N + (1/N) [f(i) + f(N-1-i)] ... summing i over [0,N-1]

If that\'s right, then the sum is strange. summing the terms separately:
f(i) = f(0) + f(1) + ... + f(N-1)
f(N-1-i) = f(N-1) + f(N-2) + ... + f(1) + f(0)

Those sum are the same. So f(N) = (N-2)/N + (2/N) f(i)

That works for small N.

f(2) = (2 - 2)/2 + (2/2)[ f(0) + f(1) ] = 0/3 + 1(0 + 0) = 0
f(3) = (3 - 2)/3 + (2/3)[ f(0) + f(1) + f(2) ] = 1/3 + (2/3)(0 + 0 + 0) = 1/3
f(4) = (4 - 2)/4 + (2/4)[ 0 + 0 + 0 + 1/3 ] = 1/2 + 1/6 = 2/3

Note that f(2) = (2-2)/3 and f(3) = (3-2)/3 to fit the pattern to be proved. Use those as base cases and proceed by induction. Suppose the statement is true for all 1 < n <= N for some specific N>1. (That\'s the case for N=3, shown above.)

Then by the given formula:
f(N+1) = (N+1-2)/(N+1) + [2/(N+1)] [ f(0) + f(1) + ... + f(N) ]


But the first three terms of the sum are 0, and the induction hypothesis says the remaining ones are:  
(3-2)/3 + (4-2)/3 + ... + (N-2)/3 = [1 + 2 + 3 + ... + (N-2)]/3
+ 4 + 5 + ... + N)/3 - 2(N-2)/3
= (N-2)(N-1)/2 * 1/3

Multiplying that by 2/(N+1) and plugging into the formula:

f(N+1) = (N - 1)/(N + 1) + (N-2)(N-1)/[3(N+1)]

Multiply the first term by 3/3 to get a common denominator:
= [3(N-1) + (N-2)(N-1)] / [3(N+1)]
= [(3 + N - 2)(N-1)] / [3(N+1)]
= (N+1)(N-1)/[3(N+1)] = (N-1)/3  
f(N+1) = [(N+1) - 2] / 3

So there you go. If the formula works for all 1<n<=N, it works for n=N+1 too. By induction, it works for all n>1. That\'s just from the given formula.