edit this page

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

St000045
Binary trees ⟶ ℤ
The number of linear extensions of a binary tree.
St000050
Binary trees ⟶ ℤ
The depth/height of a binary tree.
St000051
Binary trees ⟶ ℤ
The size of the left subtree of a binary tree.
St000061
Binary trees ⟶ ℤ
The number of nodes on the left branch of a binary tree.
St000082
Binary trees ⟶ ℤ
The number of elements smaller than a binary tree in Tamari order.
St000083
Binary trees ⟶ ℤ
The number of left oriented leafs of a binary tree except the first one.
St000118
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [.,[.,[.,.]]] in a binary ....
St000121
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [.,[.,[.,[.,.]]]] in a bin....
St000122
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [.,[.,[[.,.],.]]] in a bin....
St000125
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [.,[[[.,.],.],.
St000126
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [.,[.,[.,[.,[.,.]]]]] in a....
St000127
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [.,[.,[.,[[.,.],.]]]] in a....
St000128
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [.,[.,[[.,[.,.]],.]]] in a....
St000129
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [.,[.,[[[.,.],.],.]]] in a....
St000130
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [.,[[.,.],[[.,.],.]]] in a....
St000131
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [.,[[[[.,.],.],.],.
St000132
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [[.,.],[.,[[.,.],.]]] in a....
St000161
Binary trees ⟶ ℤ
The sum of the sizes of the right subtrees of a binary tree.
St000196
Binary trees ⟶ ℤ
The number of occurrences of the contiguous pattern [[.,.],[.,.
St000198
Binary trees ⟶ ℤ
A decimal representation of a binary tree as a code word.
St000201
Binary trees ⟶ ℤ
The number of leaf nodes in a binary tree.
St000203
Binary trees ⟶ ℤ
The number of external nodes of a binary tree.
St000204
Binary trees ⟶ ℤ
The number of internal nodes of a binary tree.
St000252
Binary trees ⟶ ℤ
The number of nodes of degree 3 of a binary tree.
St000385
Binary trees ⟶ ℤ
The number of vertices with out-degree 1 in a binary tree.
St000396
Binary trees ⟶ ℤ
The register function (or Horton-Strahler number) of a binary tree.
St000398
Binary trees ⟶ ℤ
The sum of the depths of the vertices (or total internal path length) of a binary....
St000399
Binary trees ⟶ ℤ
The external path length of a binary tree.
St000409
Binary trees ⟶ ℤ
The number of pitchforks in a binary tree.
St000411
Binary trees ⟶ ℤ
The tree factorial of a binary tree.
St000412
Binary trees ⟶ ℤ
The number of binary trees with the same underlying unordered tree.
St000414
Binary trees ⟶ ℤ
The binary logarithm of the number of binary trees with the same underlying unord....
St000568
Binary trees ⟶ ℤ
The hook number of a binary tree.
St000569
Binary trees ⟶ ℤ
The sum of the heights of the vertices of a binary tree.
St000701
Binary trees ⟶ ℤ
The protection number of a binary tree.
St000919
Binary trees ⟶ ℤ
The number of maximal left branches of a binary tree.

6. Maps

We have the following 22 maps in the database:

Mp00008
Binary trees ⟶ Ordered trees
to complete tree
Mp00009
Binary trees ⟶ Binary trees
left rotate
Mp00010
Binary trees ⟶ Ordered trees
to ordered tree: left child = left brother
Mp00011
Binary trees ⟶ Graphs
to graph
Mp00012
Binary trees ⟶ Dyck paths
to Dyck path: up step, left tree, down step, right tree
Mp00013
Binary trees ⟶ Posets
to poset
Mp00014
Binary trees ⟶ Permutations
to 132-avoiding permutation
Mp00015
Binary trees ⟶ Ordered trees
to ordered tree: right child = right brother
Mp00016
Binary trees ⟶ Binary trees
left-right symmetry
Mp00017
Binary trees ⟶ Permutations
to 312-avoiding permutation
Mp00018
Binary trees ⟶ Binary trees
left border symmetry
Mp00019
Binary trees ⟶ Binary trees
right rotate
Mp00020
Binary trees ⟶ Dyck paths
to Tamari-corresponding Dyck path
Mp00029
Dyck paths ⟶ Binary trees
to Tamari-corresponding binary tree
Mp00034
Dyck paths ⟶ Binary trees
to binary tree: up step, left tree, down step, right tree
Mp00049
Ordered trees ⟶ Binary trees
to binary tree: left brother = left child
Mp00050
Ordered trees ⟶ Binary trees
to binary tree: right brother = right child
Mp00061
Permutations ⟶ Binary trees
to increasing tree
Mp00072
Permutations ⟶ Binary trees
binary search tree: left to right
Mp00139
Ordered trees ⟶ Binary trees
Zeilberger's Strahler bijection
Mp00140
Dyck paths ⟶ Binary trees
logarithmic height to pruning number
Mp00141
Binary trees ⟶ Dyck paths
pruning number to logarithmic height

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