Binary tree

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

Figure: b110530a

These three are all different.

The number of binary trees with nodes, left children, right children () is

The numbers are called Runyon numbers or Narayama numbers.

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:

Figure: b110530b

A complete binary tree has an odd number of nodes, say , and then the number of leaves is . Label the leaves from left to right with symbols . Then the various complete binary trees with their leaves labelled in this order precisely correspond to all the different ways of putting brackets in the word , 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 nodes, is the Catalan number

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 and the free magma on .

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)
[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)