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 outgoing
branch), 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.