Given a distribution P on letters, find the lowest-cost tree.

To find the lowest-cost tree, we can use Huffman coding algorithm.

1. First, we sort the letters by their probabilities in non-increasing order.

2. Then, we create a binary tree where each leaf node represents a letter and the probability of that letter.

3. We take the two letters with the lowest probabilities and merge them into a new node with probability equal to the sum of their probabilities.

4. We repeat step 3 until we have only one node left, which is the root of the tree.

5. Finally, we assign 0 to the left branch and 1 to the right branch for each internal node.

The resulting binary tree is the lowest-cost tree for the given distribution P on letters. It can be used to encode the letters with variable-length codes, where the code for each letter is the sequence of 0s and 1s on the path from the root to the leaf representing that letter. The average code length is equal to the expected length of the codes, which is the sum of the product of the probability and the code length for each letter.