<> Definition & Example ==================== - A **binary tree** is a rooted tree where each node is either *internal* (has two children) or is a *leaf* (has no children). - Equivalently, a **binary tree** is recursively defined to be either an empty tree (*leaf*) or an ordered pair of binary trees (*internal node*). <> - The graphical representation omits the leafs and only shows the internal nodes. - There are $\operatorname{Cat}(n) = \frac{1}{n+1}\binom{2n}{n}$ binary trees with $n$ internal nodes, see [OEIS:A000108](http://oeis.org/A000108). Additional information ====================== **Feel free to add further information on the combinatorics of binary trees here!** References ========== - [Wikipedia](https://en.wikipedia.org/wiki/Binary_tree) <> Sage examples ============= {{{#!sagecell for n in [2,3,4]: BTs = BinaryTrees(n) print n, BTs.cardinality() for bt in BinaryTrees(3): print bt }}} Technical information for database usage ======================================== - A binary tree is uniquely represented as **a dot** (empty tree) or as a **sorted list of binary trees**. - Binary trees are **graded by the number of internal nodes**. - The database contains all binary trees of size at most 8.