Queries for Binary trees: search statistic / browse statistics / browse maps from / browse maps to

# 1. 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 5 Binary trees of size 3 | ||||

[.,[.,[.,.]]] |
[.,[[.,.],.]] |
[[.,.],[.,.]] |
[[.,[.,.]],.] |
[[[.,.],.],.] |

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

# 2. Additional information

**Feel free to add further information on the combinatorics of binary trees here!**

# 3. References

# 4. Sage examples

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