Countability of a binary tree

Question

Problem:

We'll define a binary tree as a tree where the degree of every internal node is exactly 3. Show that the set of all binary trees is countable.

My attempt:

A set is countable if it is finite or there is a one-to-one correspondence with the natural numbers. So we need to show that a strategy for an enumeration exists. I'm not sure exactly how detailed I'm supposed to be here, but I just tried to give a general way in which one could enumerate the set of binary trees as defined above...

Assign the first k_0 positive integers for each binary tree with height 0, then assign the next positive integers for each binary tree having height 1, and so on. The set of all binary trees can be enumerated this way and is thus countable.

Is the above the right way to go about this problem? (I'm not sure if I'm supposed to provide a specific function for how many binary trees there are at any given height k.) Thanks.

Answer 1

To show countability we need not alway show one-to-one onto mapping to $\cal N$. We can instead show a one-to-one onto mapping to a subset of $\cal N$.

Answer 2

It depends how constructive you want your proof to be. The proof you have given seems OK (as long as you point out that there are finitely many binary trees of each height $k$) but it might be possible to do it more elegantly. Here is a sketch.

Every binary tree is one of the following:

• A node which has no children.
• A node whose left child is a binary tree and which has no right child.
• A node which has no left child, and whose right child is a binary tree.
• A node which has a left child and a right child, each of which is a binary tree.

So proceed as follows:

• Label the node with no children as "0".
• Label the node with a left child only as "1", followed by the complete labelling of the child tree.
• Label the node with a right child only as "2", followed by the complete labelling of the child tree.
• Label the tree with a left and a right child as "3", followed by the complete labelling of the left child tree, followed by the complete labelling of the right child tree.

(The process is, in other words, recursive).

So every binary tree is mapped into a unique finite sequence of digits "0", "1", "2" and "3". You could interpret them as base 4, if you wanted, or stick to base 10. Not every number corresponds to a binary tree, but every binary tree corresponds to a number, and since the natural numbers are countable, so are the binary trees.

The only advantage over your proof is the aesthetic one that given a tree you can find a number and given a number you can find its tree.