the problem is this:
Consider all binary trees with roots where the vertices are not labeled and inner vertices have exactly 2 children. (See below for example trees with 3 and 5 vertices.)
Give a coding $f: \text{trees} \rightarrow \{0,1\}^*$ of the trees such that $ \mid f \mid \in O(n), $where $n$ ist the number of vertices of the tree; that is, the length of the coding is bounded by some linear function in $n$.
Attempted solution:
Consider the following coding:
$f(t)=a_1a_2...a_n$, where
$ a_i =$ $ \\ \begin{cases} 1, \text{if $v_i$ has 2 children} \\ 0, \text{if $v_i$ has no children.} \end{cases} $
Here, $v_i$ is simply the ith vertex in the graph, counting normally from the upper left corner to the lower right corner. Here are examples:
(Sorry for having really ugly graphs..) The code for the first, second, and third graph are: 100, 11000 and 10100.
Appearently the size of the coding is $n$ in the case of $n$ vertices.
It seems more of less convincing to me, but I have a feeling as if something is missing here, isn't this too easy? Do I need to prove something else?
Thanks for any suggestions...