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.