Binary Trees

# 1. Definition

A binary tree is recursively defined by being either a *leaf* (empty tree) or a pair of binary trees grafted on an internal node. They actually correspond to planar trees where each internal node has exactly two subtrees.

The size of a binary tree is its number of internal nodes.

# 2. Examples

Binary trees of size 1: (the root is on the top and the leafs are not represented)

Binary trees of size 2:

Binary trees of size 3:

Binary trees of size 4:

# 3. Properties

Binary trees are counted by the Catalan number $\operatorname{Cat}_n = \frac{1}{n+1} \binom{2n}{n}$.

# 4. Remarks

The rational numbers can be represented with the Calkinâ€“Wilf tree, a binary tree. Some statistical properties of this tree can be found here. In addition, the real numbers on the interval [0,1] can be represented by a path on a binary tree [Fer01]. Thus, the number of nodes on an infinite binary tree is countably infinite since there is a 1 to 1 mapping to the rationals, but the number of paths is uncountably infinite.

# 5. Statistics

We have the following **25 statistics** in the database:

# 6. Maps

We have the following **13 maps** in the database:

# 7. References

*The cardinality of the set of real numbers*, 2001, http://arxiv.org/vc/math/papers/0108/0108119v1.pdf.

# 8. Sage examples