Binary Trees

Contents

  1. Definition
  2. Examples
  3. Properties
  4. Remarks
  5. Statistics
  6. Maps
  7. References
  8. Sage examples

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 on Binary trees in the database:

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

6. Maps

We have the following 22 maps in the database:

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