# Homework Help: Countability of binary trees

Tags:
1. Feb 22, 2016

### goraemon

1. The problem statement, all variables and given/known data
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.

2. Relevant equations
A set is countable if it is finite or there is a one-to-one correspondence with the natural numbers.

3. The attempt at a solution
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.

2. Feb 22, 2016

### andrewkirk

That way would work. I expect your lecturer will want your proof to be somewhat more formal though.
To formalise it, prove that, for any tree T, with height k, there will be a natural number n to which it corresponds. One way to do that is to find an upper bound to the number your approach will assign to the tree (expressed in terms of k), thereby ensuring that the number-assigning algorithm terminates for that tree.