# Tree formalisms

The intuitive notion of a tree in mathematics is quite straightforward. However, there are several different formalisms of the tree concept. The link http://ncatlab.org/nlab/show/tree lists several possibilities. I would like to have an exhaustive list of all existing tree formalisms. Any references to such a source will be much appreciated. Otherwise, any tree formalism other than those appearing in the link will be appreciated.

I'm particularly interested in comparing the resulting categories of trees and noting where a particular formalism is useful and, if possible, point to the particular aspect of the formalism that makes it suitable for a particular application. So hopefully each formalism of trees will also have a notino of morphism of trees yielding a category. Different definitions of tree can yield radically different categories. Thanks!

-

I don't know much about tree representations, but looking at your list I haven't seen the (binary) tree as an expression in algebra:

$$\langle A, \bot, (\bullet, \bullet) \rangle,$$

where $A$ is the set of all expressions that could be generated from this algebra. For example, a leaf $\bot$, the smallest tree $(\bot, \bot)$, a tree of height one $((\bot,\bot),\bot)$. Often the leaf $\bot$ is denoted as $()$ and what you get is just parentheses expressions generated by simple CFG grammar (in here you get collection of $n$-ary trees, e.g. $(()()())(()()()())$ would be two trees of degree 3 and 4):

$$T \to T(T) \mid \varepsilon.$$

If you need more than the structure, then the binary tree could be denoted as (e.g. from Haskell):

BTree α = Leaf | Node (BTree α) α (BTree α)


where $\alpha$ is some type parameter. When you get bored, you can make it into a generating function:

\begin{align} T[\alpha] &= 1 + T[\alpha] \times \alpha \times T[\alpha] \\ 0 &= \alpha \times T^2[\alpha] - T[\alpha] + 1 \\ T_1[\alpha] &= \frac{1-\sqrt{1-4\alpha}}{2\alpha} \\ T_2[\alpha] &= \frac{1+\sqrt{1-4\alpha}}{2\alpha} \end{align} The first solution $T_1[\alpha]$ coincides with the generating function of Catalan numbers which not by chance describes the number of binary trees of size $n$. So $\frac{1-\sqrt{1-4\alpha}}{2\alpha}$ (the second root has a pole at zero) could be expanded into a infinite sum $\sum_{n=0}^{\infty}c_n\alpha^n$ and we gain one more representation of (binary) trees as the following: $$T[\alpha] = \coprod_{n=0}^{\infty} c_n\alpha^n$$ where $c_n$ are the Catalan numbers: 1, 1, 2, 5, 14, 42, etc.

Finally, if you don't like binary trees, you could use left-son, right-brother trick or play with some $n$-ary tree representation like this one:

Tree α = Node α (List (Tree α))
List β = Nil | Cons β (List β)


I hope it helps ;-)

-
Sadly this only gives binary trees (as you note). I think this is a special case of 'trees as operations' from the link. – Ittay Weiss Jan 7 '13 at 8:46
Well, no. You could easily extend this algebra for arbitrary finite rooted trees using some list-like construction. However what would you get is just what I have described at the bottom of the post (the left-son, right-brother trick is just a smart way of using single operator $(\bullet, \bullet)$ for two purposes). – dtldarek Jan 7 '13 at 8:50
@IttayWeiss As for the second part of the comment, this indeed looks like a special case of 'trees as operations', but in informatics and combinatorics I've hardly seen the one from the link, but very often those I presented in the post. However, since you are interested in resulting categories, I guess for you it might make no difference. – dtldarek Jan 7 '13 at 8:59
I'm not entirely sure what would be the corresponding morphisms for this formalism. – Ittay Weiss Jan 7 '13 at 9:00