weighted path length

Given an extended binary treeMathworldPlanetmath T (that is, simply any complete binary treeMathworldPlanetmathPlanetmath, where leafs are denoted as external nodes), associate weights with each external node. The weighted path length of T is the sum of the productPlanetmathPlanetmath of the weight and path length of each external node, over all external nodes.

Another formulation is that weighted path length is wjlj over all external nodes j, where wj is the weight of an external node j, and lj is the distance from the root of the tree to j. If wj=1 for all j, then weighted path length is exactly the same as external path lengthMathworldPlanetmath.


Let T be the following extended binary tree. Square nodes are external nodes, and circular nodes are internal nodesPlanetmathPlanetmath. Values in external nodes indicate weights, which are given in this problem, while values in internal nodes represent the weighted path length of subtrees rooted at those nodes, and are calculated from the given weights and the given tree. The weight of the tree as a whole is given at the root of the tree.

This tree happens to give the minimum weighted path length for this particular set of weights.

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