External Path Length

ExtendedBinaryTree

The sum over all external (square) nodes of the lengths of the paths from the root of an extended binary tree to each node. For example, in the tree above, the external path length is 25 (Knuth 1997, pp. 399-400). The internal and external path lengths are related by

where is the number of internal nodes.

See also

Extended Binary Tree, Internal Path Length

Explore with Wolfram|Alpha

More things to try:

References

Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.

Referenced on Wolfram|Alpha

External Path Length

Cite this as:

Weisstein, Eric W. "External Path Length." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ExternalPathLength.html

Subject classifications