Namespaces
Variants
Actions

Binary tree

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 05C05 [MSN][ZBL]

A (planar) rooted tree for which every node has a left child, a right child, neither, or both. Three examples are:

These three are all different.

The number of binary trees with $n$ nodes, $p$ left children, $q$ right children ($p+q=n-1$) is

$$\frac{1}{n}\binom{n}{p}\binom{n}{p+1} = \frac{1}{n}\binom{n}{p}\binom{n}{q}.$$

The numbers $\frac{1}{n}\binom{n}{p}\binom{n}{p+1}$ are called Runyon numbers or Narayana numbers (OEIS sequence A001263).

A complete binary tree is one in which every node has both left and right children or is a leaf (i.e., has no children). E.g., there are two complete binary trees with five nodes:

A complete binary tree has an odd number of nodes, say $2k+1$, and then the number of leaves is $k+1$. Label the $k+1$ leaves from left to right with symbols $x_1,\dotsc,x_{k+1}$. Then the various complete binary trees with their $k+1$ leaves labelled in this order precisely correspond to all the different ways of putting brackets in the word $x_1\cdots x_{k+1}$, each way corresponding to a computation of the product by successive multiplications of precisely two factors each time. The number of ways of doing this, and hence the number of binary trees with $k+1$ nodes, is the Catalan number

$$\frac{1}{k+1}\binom{2k}{k},k=1,2,\dotsc$$

which is OEIS sequence A000108.

The problem of all such bracketings of a product (of numbers) was considered by E. Catalan in 1838 [a1].

The correspondence between complete binary trees and (complete) bracketings gives a bijection between complete binary trees with leaves labelled with elements from a set $X$ and the free magma on $X$.

References

  • [a1] E. Catalan, "Note sur une équation aux différences finies" J. Math. Pures Appl. , 3 (1838) pp. 508–516
  • [a2] L. Comtet, "Advanced combinatorics" , Reidel (1974) Zbl 0283.05001
  • [a3] I.M. Gessel, R.P. Stanley, "Algebraic enumeration" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovacz (ed.) , Handbook of Combinatorics , II , Elsevier (1995) pp. 1021–1062
  • [a4] R.P. Stanley, "Enumerative combinatorics" , Wadsworth and Brooks/Cole (1986)
How to Cite This Entry:
Binary tree. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Binary_tree&oldid=54373
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article