algorithm design techniques character code frequency total bits space newline total figure optimal prefix code huffman' algorithm throughout this section we will assume that the number of characters is huffman' algorithm can be described as followswe maintain forest of trees the weight of tree is equal to the sum of the frequencies of its leaves - timesselect the two treest and of smallest weightbreaking ties arbitrarilyand form new tree with subtrees and at the beginning of the algorithmthere are single-node trees--one for each character at the end of the algorithm there is one treeand this is the optimal huffman coding tree worked example will make the operation of the algorithm clear figure shows the initial forestthe weight of each tree is shown in small type at the root the two trees of lowest weight are merged togethercreating the forest shown in figure we will name the new root so that future merges can be stated unambiguously we have made the left child arbitrarilyany tiebreaking procedure can be used the total weight of the new tree is just the sum of the weights of the old treesand can thus be easily computed it is also simple matter to create the new treesince we merely need to get new nodeset the left and right pointersand record the weight now there are six treesand we again select the two trees of smallest weight these happen to be and twhich are then merged into new tree with root and weight sp nl figure initial stage of huffman' algorithm sp figure huffman' algorithm after the first merge nl