Binary tree

From Encyclopedia of Mathematics
Revision as of 17:28, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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 .


[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)
How to Cite This Entry:
Binary tree. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article