nl sp figure slightly better tree notice that the tree in figure is full treeall nodes either are leaves or have two children an optimal code will always have this propertysince otherwiseas we have already seennodes with only one child could move up level if the characters are placed only at the leavesany sequence of bits can always be decoded unambiguously for instancesuppose is the encoded string is not character code is not character codebut represents iso the first character is then followsgiving an then followswhich is newline the remainder of the code is aspacetieand newline thusit does not matter if the character codes are different lengthsas long as no character code is prefix of another character code such an encoding is known as prefix code converselyif character is contained in nonleaf nodeit is no longer possible to guarantee that the decoding will be unambiguous putting these facts togetherwe see that our basic problem is to find the full binary tree of minimum total cost (as defined above)where all characters are contained in the leaves the tree in figure shows the optimal tree for our sample alphabet as can be seen in figure this code uses only bits notice that there are many optimal codes these can be obtained by swapping children in the encoding tree the main unresolved questionthenis how the coding tree is constructed the algorithm to do this was given by huffman in thusthis coding system is commonly referred to as huffman code nl figure optimal prefix code sp