Enumerating Trees (2013)

A one-to-one mapping between binary trees and natural numbers.

A binary tree is either empty, or it has two binary trees as children. Following is a technique for mapping non-negative integers to binary trees in an efficient manner.

To de-interleave a number I write it in binary and create two numbers from it, one using the odd bits and the other the even bits. For example, to de-interleave 71 I’d write it in binary as 1000111 then I’d take the odd bits 1 0 0 0 1 1 1 to make 1011, which is 11, and the even bits 1 0 0 0 1 1 1 to make 001, which is 1; thus 71 becomes (11, 1).

The tree for a number n is empty is n is zero; otherwise it has as its two children the trees for the de-interleaving of n − 1

As far as I know, a dense enumeration of binary trees such as this has never before been published. The existence of things like Boltzman samplers and other techniques for generating random trees supports this assumption, since random trees with this mapping are as easy to generate as are random numbers.

If your browser supports javascript, below are the first 50 binary trees using this enumeration.