Question

a) What is a prefix code?

b) How can a prefix code be represented by a binary tree?

Short answer

A prefix code is a coding of letters with the property that a bit string corresponding with a letter is never the beginning of a string of another letter.

One can encode a prefix code with a binary tree, by creating a rooted tree with two children. The edge of the left child is labeled \(0\) and the edge of the right child is labeled \(1\). Similarly, assign one or two children to every vertex until every path from the root to a leaf uniquely represents the encoding of a letter.

Step-by-step solution

Definition

A tree is an undirected graph that is connected and that does not contain any simple circuits.

The preorder traversal of a tree \({\bf{T}}\) with root \({\bf{r}}\) begins by visiting \({\bf{r}}\), then the most left subtree at \({\bf{r}}\) in preorder, then the second most left subtree at \({\bf{r}}\) in preorder, and so on.

A prefix code encodes letters such that the bit string for a letter never occurs as the beginning of the bit string for another letter.

Binary tree

One can encode a prefix code with a binary tree, by creating a rooted tree with two children. The edge of the left child is labeled \(0\) and the edge of the right child is labeled \(1\). Similarly, assign one or two children to every vertex until every path from the root to a leaf uniquely represents the encoding of a letter.

For example, the encoding \({\bf{a = 0, b = 10}}\) and \({\bf{c = 11}}\) can be represented by the following binary tree.