# 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 ExternalPathLength 2013-03-22 12:32:03 2013-03-22 12:32:03 Logan (6) Logan (6) 4 Logan (6) Definition msc 05C05 ExtendedBinaryTree WeightedPathLength external path length internal path length