Binary Tree

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

A binary tree is a tree-like structure that is rooted and in which each vertex has at most two children and each child of a vertex is designated as its left or right child (West 2000, p. 101). In other words, unlike a proper tree, the relative positions of the children is significant.

Dropping the requirement that left and right children are considered unique gives a true tree known as a weakly binary tree (in which, by convention, the root node is also required to be adjacent to at most one graph vertex).

The height of a binary tree is the number of levels within the tree. The numbers of binary trees of height 👁 h=1
, 2, ... nodes are 1, 3, 21, 651, 457653, ... (OEIS A001699). A recurrence equation giving these counts is

with 👁 a_1=1
.

The number of binary trees with 👁 n
nodes are 1, 2, 5, 14, 42, ... (OEIS A000108), which are the Catalan number 👁 C_n
.

For a binary tree of height 👁 h
with 👁 n
nodes,

These extremes correspond to a balanced tree (each node except the tree leaves has a left and right child, and all tree leaves are at the same level) and a degenerate tree (each node has only one outgoing branch), respectively.

For a search of data organized into a binary tree, the number of search steps 👁 S(n)
needed to find an item is bounded by

Partial balancing of an arbitrary tree into a so-called AVL binary search tree can improve search speed.

See also

B-Tree, Calkin-Wilf Tree, Cayley Tree, Complete Binary Tree, Extended Binary Tree, Heap, Quadtree, Red-Black Tree, Rooted Tree, Splay Tree, Stern-Brocot Tree, Strongly Binary Tree, Trivalent Tree, Weakly Binary Tree

Explore with Wolfram|Alpha

References

Lucas, J.; Roelants van Baronaigien, D.; and Ruskey, F. "Generating Binary Trees by Rotations." J. Algorithms 15, 343-366, 1993.Ranum, D. L. "On Some Applications of Fibonacci Numbers." Amer. Math. Monthly 102, 640-645, 1995.Ruskey, F. "Information on Binary Trees." http://www.theory.csc.uvic.ca/~cos/inf/tree/BinaryTrees.html.Ruskey, F. and Proskurowski, A. "Generating Binary Trees by Transpositions." J. Algorithms 11, 68-84, 1990.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 35, 1990.Skiena, S. S. The Algorithm Design Manual. New York: Springer-Verlag, pp. 177-178, 1997.Sloane, N. J. A. Sequences A000108/M1459, A001190/M0790, and A001699/M3087 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 101, 2000.

Referenced on Wolfram|Alpha

Binary Tree

Cite this as:

Weisstein, Eric W. "Binary Tree." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BinaryTree.html

Subject classifications