1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Countability of binary trees

  1. Feb 22, 2016 #1
    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. jcsd
  3. Feb 22, 2016 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted