# Average number of full nodes in a binary search tree

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!

• what have you considered? tried? what ideas do you have on attacking the problem? – nneonneo Oct 19 '12 at 2:36

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.
• I think you are on the right way. But I think you made a mistake, since the equation for f holds for n>1. You have to throw out the cases when i=0,1,N-2, N-1. I tried it, but the result is still not the same. – Nejc Oct 22 '12 at 15:15