Let’s look at the problem of generating all binary (degree-2) tree structures.

There are probably multiple approaches to doing this, but the conceptually easiest approach exploits the recursive nature of tree generation.

Consider the tree-of-trees depicted below:

At the top we start with the simplest possible binary tree, which is a single node with no children. This simplest tree has depth d=0. To produce all trees of depth d=1, we simply augment the d=0 tree with every possible combination of children assignments. In a binary tree, a node can have 0, 1, or 2 children. Since the 0-child descendant is identical to the parent we ignore it, producing the two descendants depicted.

We can repeat this process to produce the d=2 binary trees. However, things are not quite as straightforward when we have more than one node accepting children.

If there are 2+ nodes at the deepest level in the parent tree, it turns out what we are specifically interested in is the k-combinations-with-replacement of child count assignments to these nodes.

For example, let’s look at the second d=1 tree, which has two children at its deepest level.

The 2-combinations without replacement would look like: [0 1][0 2][1 2]. The combination [0 1] can be interpreted as “the first child gets no children and the second child gets one child”.

The 2-combinations with replacement would look like: [0 0][0 1][0 2][1 1][1 2][2 2].

The combinations with replacement give us all of the possible descendant tree structures.

In fact, we can represent an entire binary tree as just a list of child assignments. For example the first tree depicted in this post above can be represented as [[1][1][2][1 1]]. To expand this tree we would simply find n = number of children in the the deepest level (here [1 1] is the deepest level and thus n=2) and cross the parent structure with all n-combinations with replacement. Easier expressed in code:

(defn expand-tree

  [t]

  (for [c (rest

            (k-combos

              (reduce + (last t))

              3))]

    (conj t c)))

With this expansion function we can use a simple queue to walk breadth-first the “hyper-tree” of all binary trees. Here are the first 750 of such structures:

 

Here is the full gist to produce the sequence of all binary tree structures.