Bird tree

Posted on March 16, 2014 by phimuemue

I came across a very nice method of enumerating the positive rational numbers based on a particular tree. This post explains how this tree is constructed and shows that actually all positive rational numbers are contained in this tree.

Bird tree definition

The tree itself is defined in a very simple manner:

A very simplistic implementation in Haskell could look as follows:

data BirdTree a = Node a (BirdTree a) (BirdTree a)

instance Functor BirdTree where
    fmap f (Node e l r) = Node (f e) (fmap f l) (fmap f r)

bird = Node 1
    (fmap (\b -> 1/(b+1)) bird)
    (fmap (\b -> (1/b) + 1) bird)

Let's consider the first levels of the Bird tree:

                   /   \
                  /     \
                 /       \
              1/2         2/1
             /   \       /   \
           2/3   1/3   3/1   3/2

All positive rationals are contained in the Bird tree

It can be shown quite easily that all positive rationals are contained in this tree. We do so by first defining two functions:

We can use this functions to "traverse" the tree in a very straightforward manner:

Let us also construct the respective inverse functions of \(l\) and \(r\):

If we now want to prove that any \(q\in\mathbb{Q}\) is contained in the tree, we want to prove that - given any \(q\) - we can find functions \(f_1,\dots,f_n \in \left\{ l, r\right\}\) such that \(f_1(f_2(\dots f_n(1))) = q\).

We transform this claim (by using the inverse functions) into the following: We can find - given any \(q\in\mathbb{Q}\) functions \(f_1^{-1},\dots,f_n^{-1}\in\left\{ l^{-1}, r^{-1}\right\}\) such that \(f_n^{-1}(f_{n-1}^{-1}(\dots f_2^{-1}(f_1^{-1}(q))))=1\).

Euclid to the rescue

This might not look like a simplification at first sight, but we can compute the following:

Let us use - for a short intermezzo - use another notation for fractions: Instead of the fraction \(\frac{a}{b}\) we write the pair \((a, b)\). Extending this notation, the functions \(r^{-1}\) resp. \(l^{-1}\) map the pair \((a,b)\) to \((b, a-b)\) resp. \((b-a, a)\). Now, our only goal is to prove that we can "concatenate" these functions in a way such that we eventually reach a pair \((c,c)\) for some \(c\in\mathbb{N}\).

This, however, is a well known fact: If we have a pair \((a, b)\), we can have three cases:

It is clear that this routine finally produces a pair with two equal numbers - it corresponds to Euclids algorithm for finding the greatest common divisor.

Testing stuff

We can transform our knowledge into a small piece of software:

-- The functions l and r...
r x = (1 / x) + 1
l x = 1 / (x + 1)

-- ... and their inverse counterparts
_l x = 1/x - 1
_r x = 1/(x - 1)

-- find a certain element
find 1 = []
find q = if q > 1 then 1:(find (_r q)) else 0:(find (_l q))

The result of find a is a list of zeroes and ones, where 1 indicates that you should go right and 0 indicates that you should go left.

We write a quick test routine to ensure that our finding routine actually works.

-- traverse tree according to a specific route
traverse :: BirdTree a -> [Integer] -> Maybe a
traverse (Node e l r) seq = case seq of
    [] -> Just e
    (x:xs) -> traverse (if x==0 then l else r) xs

-- check results with the following:
-- traverse bird $ find (123/345)