Eric Lippert - Generating All Binary Trees

I used to describe a small algorithm that did small operations on binary trees. I wanted to test it. I tried several small tests and they passed, but I was not happy. I was almost certain, but perhaps some kind of incomprehensible topology of a binary tree could lead to an error. I realized that there is a finite number of binary trees of a given size. I decided to try them all.

Before starting, I need a convenient binary tree entry. Here is the top of my tree:

class Node
{
public Node Left { get ; private set ; }
public Node Right { get ; private set ; }
public Node(Node left, Node right)
{
this .Left = left;
this .Right = right;
}
}

* This source code was highlighted with Source Code Highlighter .

Everything is very simple: the left node, the right node and all. Please note that in order to make this article more understandable, I have removed the data from the vertex, which is usually stored in a binary tree. Let's assume these are ordinary numbers. I will represent the tree as a compact string. The empty link in the tree is denoted by x. The non-empty vertex in my “tree without values” will be denoted (<left descendant> <right descendant>). Consider a tree:
one
/ \
x 2
/ \
x x

Vertex 2 has two zero children and will be denoted by (xx). Vertex 1 has an empty left descendant, and the right descendant is vertex 2. Thus, the tree is designated as (x (xx)). What's the point? We can write a small recursive code that builds such lines:

public static string BinaryTreeString(Node node)
{
var sb = new StringBuilder ();
Action<Node> f = null ;
f = n =>
{
if (n == null )
sb.Append( "x" );
else
{
sb.Append( "(" );
f(n.Left);
f(n.Right);
sb.Append( ")" );
}
};
f(node);
return sb.ToString();
}

* This source code was highlighted with Source Code Highlighter .

How to enumerate all possible binary trees of a given size? We do this recursively.
')
There is exactly one tree with 0 vertices. It is denoted by x. This is the base.

Now choose a number. For example, four. We want to number all trees from four non-empty vertices. Suppose we have already numbered all the vertices of three, two, and one vertex. Denote the set of binary trees of n vertices as B (n). Suppose that we create all possible combinations of B (x) and B (y), meaning that B (x) corresponds to the left descendant of the root, and B (y) corresponds to the right descendant of the root. I will write B (x) B (y). In this record, trees with four non-empty vertices can be divided into four sets: B (0) B (3), B (1) B (2), B (2) B (1), B (3) (0).

It is rather simple to summarize: we can enumerate all trees with k vertices, turning over each time k cases in which we consider problems of smaller size. Remarkable recursive solution. Consider the code:

static IEnumerable <Node> AllBinaryTrees( int size)
{
if (size == 0)
return new Node[] { null };
return from i in Enumerable.Range(0, size)
from left in AllBinaryTrees(i)
from right in AllBinaryTrees(size - 1 - i)
select new Node(left, right);
}

* This source code was highlighted with Source Code Highlighter .

Note that LINQ makes the algorithm more similar to its description than the equivalent program with a large number of cycles.

And indeed, if we run:

foreach ( var t in AllBinaryTrees(4))
Console .WriteLine(BinaryTreeString(t));

* This source code was highlighted with Source Code Highlighter .

Then we get all the trees from four non-empty peaks.
(x (x (x (xx))))
(x (x ((xx) x)))
(x ((xx) (xx)))
(x ((x (xx)) x))
(x (((xx) x) x))
((xx) (x (xx)))
((xx) ((xx) x))
((x (xx)) (xx))
(((xx) x) (xx))
((x (x (xx))) x)
((x ((xx) x)) x)
(((xx) (xx)) x)
(((x (xx)) x) x)
((((xx) x) x) x)

Now I have a mechanism that builds all tree topologies, and I can test my algorithm.

How many trees are there? It seems they can be quite a lot.

The number of binary trees of n vertices is called the Catalan number, which has many interesting properties. The nth Catalan number is calculated by the formula (2n)! / (n + 1)! n !, which grows exponentially. (In Wikipedia, some evidence was suggested that this is a form of the Catalan number.) The number of binary trees of a given size

0 1
eleven
2 2
4 14
8 1430
12 208012
16 35357670

Therefore, my plan to try all the trees of this size is not very good. There are too many options and it is not possible to check everything in a short period of time.

I will puzzle you: we will forget about binary trees and for the current moment we will consider arbitrary trees. An arbitrary tree can have 0, 1, or any finite number of children. Let a non-empty arbitrary tree be written with a list of descendants in brackets. So {{} {} {{}}} is a tree.

one
/ | \
2 3 4
|
five

Because vertices 2, 3 and 5 have no descendants, they will be written as {}. What is the point? Pay attention to the order. {{} {} {{}}} and {{} {{}} {}} are different trees with a similar structure.

My first task: what more arbitrary trees from n vertices or binary trees from n vertices.
My second task: can you develop a numbering mechanism for arbitrary trees?