Is there a natural way to totally order the set of unlabeled binary trees on $n$ nodes?

Question

Let $C_n$ be the $n^{th}$ Catalan number. There are $C_n$ unlabeled binary trees having $n$ internal nodes. I want to totally order these trees in some (hopefully not too complicated) natural manner. Perhaps there is some "standard" way of doing this. When I look at pictures of, say the 14 binary trees on 4 nodes, they never seem to be listed in any particular order. Notice that what I want to order is the trees themselves not the vertices within each tree.

I tried classifying by height and then by height of shortest branches from left to right but I'm not sure if what I have is correct. I think there must be some well known way to order these trees?

Answer 1

Let $S$ and $T$ be binary trees. Provided $S$ and $T$ are nontrivial, we write $S=(S^L,S^R)$ and $T=(T^L,T^R)$. An ordering on trees is determined recursively as follows: $$ S\le T\iff \begin{cases} S=\text{trivial tree}&\text{or}\\ S^L<T^L & \text{or}\\ S^L=T^L\text{ and }S^R\le T^R \end{cases} $$ Roughly, trees are ordered in terms of simplicity, with preference given to the left subtree, so this is a recursive lexicographic order. For example, when $n=3$,

Answer 2

For $k = 0$ to $n - 1$ (or vice versa) enumerate all the possible left subtrees with $k$ nodes. For each possible left subtree with $k$ nodes, enumerate all the possible right subtrees with $n - k - 1$ nodes. Recursively, this gives for every positive integer $n$ a fairly natural way to totally order the set of all unlabeled binary trees with $n$ nodes, by referring to the same procedure to totally order the set of all trees with any given smaller number of nodes.