<>
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.