Binary Tree (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
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 
, 2, ... nodes are 1, 3, 21, 651, 457653, ... (OEIS A001699). A recurrence equation giving these counts is
 |
(1) |
|---|
with 
.
The number of binary trees with 
nodes are 1, 2, 5, 14, 42, ... (OEIS A000108), which are the Catalan number 
.
For a binary tree of height 
with 
nodes,
 |
(2) |
|---|
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 outgoingbranch), respectively.
For a search of data organized into a binary tree, the number of search steps 
needed to find an item is bounded by
 |
(3) |
|---|
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
Cite this as:
Weisstein, Eric W. "Binary Tree." FromMathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BinaryTree.html