# 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 |