external path length

Given a binary tree $T$, construct its extended binary tree $T^{\prime }$. The external path length of $T$ is then defined to be the sum of the lengths of the paths to each of the external nodes.

For example, let $T$ be the following tree.

The extended binary tree of $T$ is

The external path length of $T$ (denoted $E$) is

$$E=2+3+3+3+3+3+3=20$$

The internal path length of $T$ is defined to be the sum of the lengths of the paths to each of the internal nodes. The internal path length of our example tree (denoted $I$) is

$$I=1+2+0+2+1+2=8$$

Note that in this case $E=I+2n$, where $n$ is the number of internal nodes. This happens to hold for all binary trees.

Title	external path length
Canonical name	ExternalPathLength
Date of creation	2013-03-22 12:32:03
Last modified on	2013-03-22 12:32:03
Owner	Logan (6)
Last modified by	Logan (6)
Numerical id	4
Author	Logan (6)
Entry type	Definition
Classification	msc 05C05
Related topic	ExtendedBinaryTree
Related topic	WeightedPathLength
Defines	external path length
Defines	internal path length