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 **24 statistics** in the database:

# 6. Maps

Binary trees have some internal symmetries:

the

**left-right symmetrised**of a tree is the tree where left and right subtrees have been recursively exchanged. As an example, here is a tree and its left-right symmetrised:-

the

**left-border symmetrised**of a tree is a the tree where each left branch of the tree has been reversed. Indeed, a binary tree can be seen as an ordered set of binary trees grafted on a left branch. If a tree is formed by $T_1$, $T_2$, $T_3$ on its left branch on this order, then its left-border symmetrised, is formed by $T_3'$, $T_2'$, $T_1'$ where $T_1'$, $T_2'$, and $T_3'$ are the left-border symmetrised of respectively $T_1$, $T_2$, and $T_3$.

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

- |
- |
- |

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

Recursive maps to Dyck paths: both Dyck paths and binary trees have recursive definitions. Depending on how you read the Dyck path, you obtain different maps to binary trees. A non empty Dyck path can be read: up step, Dyck path, down step, Dyck path. The first Dyck path is then recursively mapped to the left subtree and the second one to right subtree.

Tamari map to Dyck paths: the Tamari order can be interpreted in terms of both Dyck paths and binary trees. The map that sends a binary tree to the corresponding Dyck path in the Tamary order corresponds to another recursive reading of the Dyck path. A non empty Dyck patch reads: Dyck Path, up step, Dyck path, down step. The first and second Dyck paths are respectively mapped to the left and right subtrees of the tree.

- The number of nodes of each tree is the size of its undirected graph, another undirected graph can be formed by counting the nodes and leaves. The size of the undirected graph using leaves is 2n+1 where n is the size of the undirected graph using nodes only. This mapping can be represented in sage using the t.to_undirected_graph() and t.to_undirected_graph(with_leaves=True) where t is a binary tree.

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.

- To construct a Sylvester class we must first create a binary search tree. This is done by labelling each node K such that any label in the left subtree of is less than or equal to K and any node the right subtree is greater than or equal to k. Then construct permutations such that the partial order is respected, for example:

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 size of the Sylvester class is the same as the number of linear extensions on a binary tree.
- When linear extensions are applied to binary trees, they become ordered trees.
- The 132 avoiding permutation of a binary tree is the maximal element of the Sylvester class for that tree.
- the 312 avoiding permutation is the minimal element of the Sylvester class for a binary tree.

The following maps have individual pages with further explanations:

Dyck Paths: http://www.findstat.org/DyckPaths

# 7. References

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

# 8. Sage examples