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 25 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.

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