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
We have the following 35 statistics in the database:
6. Maps
We have the following 13 maps in the database:
7. References
8. Sage examples