An extension to the external path length theorem
William J. Collins · Proceedings of the 17th conference on ACM Annual Computer Science Conference · 1989
Let T be a nonempty binary tree with L(T) leaves and H(T) height. E(T), the external path length of T, is the sum of all path lengths from the root to the leaves. In Knuth's The Art of Computer Programming, Volume 3, Sorting and Searching, page 194 (Addison-Wesley, 1973), the following is proved:External Path Length Theorem: Let T be a nonempty two-tree (i.e., each node has zero or two children). Then E(T) ≥ L(T)log2L(T).