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:

b-3-1.png b-3-2.png b-3-3.png b-3-4.png b-3-5.png

Binary trees of size 4:

b-4-1.png b-4-2.png b-4-3.png b-4-4.png b-4-5.png b-4-6.png b-4-7.png b-4-8.png b-4-9.png b-4-10.png b-4-11.png b-4-12.png b-4-13.png b-4-14.png

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

Let $B$ be the set of binary trees of size $n$.

6. Maps

Binary trees have some internal symmetries:

Here is an example of some trees and their left-border symmetrised:

b-4-6.png - b-4-10.png

b-4-3.png - b-4-4.png

b-6-example1.png - b-6-example2.png

They are many bijections between binary trees and other Catalan objects. Here are some of them:

The Sylvester class of a binary tree is the set of permuations that is yielded by converting a binary tree into a poset, and then creating linear extensions on that poset.

The tree represented by $[., [[., .], [., [., .]]]]$ has the following Sylvester class : $[[2, 5, 4, 3, 1], [5, 2, 4, 3, 1], [5, 4, 2, 3, 1]]$

The following maps have individual pages with further explanations:

7. References

[Fer01]   J. Ferreira, The cardinality of the set of real numbers, 2001, http://arxiv.org/vc/math/papers/0108/0108119v1.pdf.

8. Sage examples


CategoryCombinatorialCollection