I'm really bugging on a question I hope somebody here can help me!

If we note by $\displaystyle S_N$ the average search cost in the case of a successful search in a binary search tree and $\displaystyle U_S$ in the case of an unsuccessful search, we can say that

$\displaystyle S_N = I/N$, where $\displaystyle I$ is the internal path length and $\displaystyle N$ is the number of nodes in the tree.

Prove that $\displaystyle U_N=\frac{N}{N+1}(S_N+2)$.

and just for a reminder, $\displaystyle E =I+2N$, where $\displaystyle E$ is the external path length of a binary search tree.

REMINDER: