Countability of binary trees

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

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,836
1,418
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.
 

Related Threads on Countability of binary trees

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
0
Views
973
Replies
0
Views
2K
Replies
3
Views
4K
Replies
6
Views
775
  • Last Post
Replies
2
Views
1K
Replies
1
Views
4K
  • Last Post
Replies
2
Views
4K
Replies
0
Views
8K
Top