Upper Bounds for the Total Path Length of Binary Trees

Abstract

Two upper bounds for the total path length of binary trees are obtained. One is for node-trees, and bounds the internal (or root-to-node) path length; the other is for leaf-trees, and bounds the external (or root-to-leaf) path length. These bounds involve a quantity called the balance, which allows the bounds to adapt from the n log n behavior of a completely balanced tree to the n2 behavior of a most skewed tree. These bounds are illustrated for the case of Fibonacci trees. © 1973, ACM. All rights reserved.