Average number of full nodes in a binary search tree

Question

Let $f(N)$ be the average number of full nodes (nodes with two children) in an $N$-node binary search tree.

1. Determine the values of $f(0)$ and $f(1)$.

2. Given that for $N > 1$,

   $\qquad \displaystyle f(N) = \frac{N-2}{N} + \frac{1}{N} \sum_{i=0}^{N-1} [f(i) + f(N - i - 1)]$,

   show that $f(N) = \frac{N - 2}{3}$.

3. Using this information, show that the average number of nodes with one child in a binary search tree is $\frac{N + 1}{3}$.

I know that for (1) both values are $0$. I mainly need help proving (2). I also found some hints for (2) and (3) but I can't figure it out:

(2) The root contributes $\frac{N − 2}{N}$ full nodes on average, because the root is full as long as it does not contain the largest or smallest item. The remainder of the equation is the expected contribution of the subtrees.

(3) The average number of leaves is $\frac{N + 1}{3}$.

Any help would be appreciated, even just pointing me in the right direction. Thanks!

Answer 1

As the both the formula itself is given $f(n) = \frac{n-2}{3}$ as well as the inductive structure $f(n) = \frac{n-2}{n} + \frac1n \sum_{i=0}^{n-1}{\dots}$, it seems you are requested to show the formula by (mathematical) induction. Hint (2) only explains the formula.

Inductively you apply the formula for $f(k), k<n$ in the recursive expression and conclude that it also holds for $f(n)$. I can do that, but run into trouble. The formulas do not match.

Summing $f(i) + f(n-i-1)$ is easy, as it is equal to $\frac{i-2}3 + \frac{n-i-1-2}3 = \frac{n-5}3$, so the $i$'s cancel. Plugging it into the recursion yields $\frac{n-2}{n} + \frac nn \frac{n-5}3$ which is not the expected $\frac{n-2}{3}$.

edit: The first values of $f$ however are special. $f(0) = f(1) = 0$, where the formule $\frac {n-2}3$ predicts $\frac {-2}3$ and $\frac {-1}3$ respectively. Thus we have to correct this within the summation, twice as it occurs in both $i=0,1$ and $i=n-1,n$, and add $\frac 2n$. Amazingly, that works.

Part (3) just expects you to know what is the relation between the numbers of full nodes and leaves in a binary tree.