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)
![[.,.].png](/BinaryTrees?action=AttachFile&do=get&target=%5B.%2C.%5D.png "[.,.].png")
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
Let $B$ be the set of binary trees of size $n$.
St000050: the Depth of the tree is given recursively by: $0$ if the tree is empty (leaf), and $1 + max(depth(l), depth(r))$, if $l$ and $r$ are the respective left and right subtree of a binary tree $t$.
The upper and lower bounds on the depth of a binary tree $b$ of size $n$ are $log_2(n) \leq depth(b) \leq n$.
St000061: the number of nodes on the left branch of the tree by counting.
Using the to 312 avoiding permutations map, this corresponds to the decomposition number of a permutation, St000056.
After applying the Tamari bijection between binary trees and Dyck Paths, this counts the number of touch points of the corresponding Dyck Path, St000011.
St000051: the size of the left subtree.
St000083: the number of left oriented leaves except the first one. In other other words, this is the sum of canopee vector of the tree.
Using the to 312 avoiding permutations map, this counts the number of descents of a permutation, St000021.
After applying the Tamari bijection between binary trees and Dyck Paths, this counts the number of double rises of a Dyck path, St000024.
St000161: the sum of the sizes of the right subtree obtained by computing the size of the right subtree for each node of the binary tree and take the sum.
Using the to 312 avoiding permutations map, this is the length the permutation, St000018.
After applying the Tamari bijection between binary trees and Dyck Paths, this is the area of the Dyck path, St000012.
St000082: the number of elements smaller than the tree for the Tamari order.
Not surprisingly, after applying the Tamari bijection between binary trees and Dyck Paths, this counts the number of elements smaller than the given Dyck path in the Tamari Order, St000032
St000045: the number of linear extensions of a binary three. This as also:
The number of increasing / decreasing binary trees labelled by $1,…,n$ of this shape.
- The size of the sylvester class corresponding to this tree when the Tamari order is seen as a quotient poset of the right weak order on permutations.
- The number of permutations which give this tree shape when inserted in a binary search tree.
- The number of permutations which increasing / decreasing tree is of this shape.
St000201: the number of leaf nodes in the tree. Leaf nodes are the bottom node in the binary tree that has no children.
A000079 given by $2^{n-1}$ for $n \geq 1$, counts the number of binary trees of size $n$ with exactly one leaf node.
A001788 given by $n * (n+1) * 2^{n-2}$ for $n \geq 3$, counts the number of binary tree of sizes $n$ with exactly two leaf nodes.
After applying the to poset map, this corresponds to the number of minimal element in a poset, St000068, as well as the number of maximum chains in a poset, St000071.
Applying the to Dyck Path map followed by to 312 avoiding permutations, this corresponds to the number of peaks of a permutation, St000092.
If we first apply the to 312 avoiding permutations map, followed by the inverse map, then this corresponds to the number of valleys of a permutation, St000099.
St000203: the number of external nodes of a tree. External nodes consists of the root node, along with nodes that are recursively to the left and recursively to the right of the root of the tree.
A070031 counts the sum of all the external node of all the binary trees of size $n$. This corresponds to the expansion of $(1+x*C)*C^{3}$, where $C = \frac{1-(1-4*x)^{\frac{1}{2}}}{2*x}$ is the generating function for Catalan numbers, A000108.
St000204: the number of internal nodes of a tree. Internal nodes of the tree is obtained by subtracting the number of external nodes from the total number of nodes in the tree.
A002058 counts the number of internal triangles in all triangulations of an $(n+1)$-gon.
The number of contiguous patterns
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
8. Sage examples