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:

The number of linear extensions of a binary tree.
The depth of a binary tree.
The size of the left subtree of a binary tree.
The number of nodes on the left branch of a binary tree.
The number of elements smaller than a binary tree in Tamari order.
The number of left oriented leafs of a binary tree except the first one.
The number of occurrences of the contiguous pattern [.,[.,[.,.]]] in a binary ....
The number of occurrences of the contiguous pattern [.,[.,[.,[.,.]]]] in a bin....
The number of occurrences of the contiguous pattern [.,[.,[[.,.],.]]] in a bin....
The number of occurrences of the contiguous pattern [.,[[[.,.],.],.
The number of occurrences of the contiguous pattern [.,[.,[.,[.,[.,.]]]]] in a....
The number of occurrences of the contiguous pattern [.,[.,[.,[[.,.],.]]]] in a....
The number of occurrences of the contiguous pattern [.,[.,[[.,[.,.]],.]]] in a....
The number of occurrences of the contiguous pattern [.,[.,[[[.,.],.],.]]] in a....
The number of occurrences of the contiguous pattern [.,[[.,.],[[.,.],.]]] in a....
The number of occurrences of the contiguous pattern [.,[[[[.,.],.],.],.
The number of occurrences of the contiguous pattern [[.,.],[.,[[.,.],.]]] in a....
The sum of the sizes of the right subtrees of a binary tree.
The number of occurrences of the contiguous pattern [[.,.],[.,.
A decimal representation of a binary tree as a code word.
The number of leaf nodes in a binary tree.
The number of external nodes of a binary tree.
The number of internal nodes of a binary tree.
The number of nodes of degree 3 of a binary tree.

# 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:

# 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

BinaryTrees (last edited 2015-10-30 15:57:13 by ChristianStump)