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

We have the following 32 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.
The number of vertices with out-degree 1 in a binary tree.
The register function (or Horton-Strahler number) of a binary tree.
The internal path length of a binary tree.
The external path length of a binary tree.
The number of pitchforks in a binary tree.
The tree factorial of a binary tree.
The number of binary trees with the same underlying unordered tree.
The binary logarithm of the number of binary trees with the same underlying unord....

6. Maps

We have the following 13 maps in the database:

to complete tree
left rotate
to ordered tree: left child = left brother
to graph
to Dyck path: up step, left tree, down step, right tree
to poset
to 132-avoiding permutation
to ordered tree: right child = right brother
left-right symmetry
to 312-avoiding permutation
left border symmetry
right rotate
to Tamari-corresponding Dyck path

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