### Technical Report No. 1, October 1987 - Abstract

**Rolf Klein, Derick Wood:**

*On the Path Length of Binary Trees*

*This report is not available in electronic form!*

We show that the external path length of a binary tree is closely related to the ratios of means of certain integers and establish the upper bound

*External Path Length <= N*(log_2 N + Delta - log_2 Delta - 0.6623)*

where *N* denotes the number of external nodes in the tree
and *Delta* is the difference
in length between a longest and a shortest path.
Then we prove that this bound is
(almost) achieved if *N* and *Delta* are arbitrary integers
that satisfy
*Delta <= sqrt(N)*.
If *Delta > sqrt(N)*, we construct binary trees
whose external path length is at least as
large as

*N*(log_2 N + Phi(N,Delta)*Delta - log_2 Delta - 4)*,

where

*Phi(N,Delta) = (1 + Theta(Delta/N))^(-1)*.