- #1

- 67

- 4

## Homework Statement

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.

## Homework Equations

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

## 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.