Internal Path Length
03:46 PM
22-5-2022
1773
Author : Knuth, D. E
Book or Source : The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.
page : ...
The sum over all internal (circular) nodes of the paths from the root of an extended binary tree to each node. For example, in the tree above, the internal path length is 11 (Knuth 1997, pp. 399-400). The internal and external path lengths are related by
where is the number of internal nodes.
Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.