Namespaces
Variants
Actions

Binary tree

From Encyclopedia of Mathematics
Jump to: navigation, search

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

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners in accordance with our Privacy Policy. You can manage your preferences in 'Manage Cookies'.