On the path length of binary trees
Rolf Klein, Derick Wood · Journal of the ACM · 1989
It is shown 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 + Δ - log 2 Δ - 0.6623), where N denotes the number of external nodes in the tree and Δ is the difference in length between a longest and shortest path. Then it is proved that this bound is tight up to an o(N) term if Δ ≤ √N. If Δ > √N , we contstruct binary trees whose external path length is at least as large as N(log 2 N + Φ(N, Δ)Δ - log 2 Δ -4) , where Φ(N, Δ) = 1/(1 + 2(Δ/N)) .