A binary tree is a type of data structure used in computer programming to store, sort, and access information. Binary trees are the simplest variety of tree, but are very useful and easy to implement. A typical implementation of a binary tree relies on a root node linked to a series of nodes that make up the tree itself by pointer variables. This type of tree derives its name from the fact that no node within the tree can have more than two children.
Tree data structures come in many varieties. They are made up of different nodes, which are organized in a hierarchical pattern. A single node, the root, is the access point through which the entire data tree can be searched or otherwise manipulated. This root node points to the top node within the tree itself.
Any node within a tree, save for the topmost node, will have a parent node which is located above it in the hierarchy of the tree. It can also have child nodes, which are located below it. A given node is accessed through those above it in the tree and provides access to those below it.
Binary tree data structures allow each node to have no more than two children. A given node can thus have zero, one, or two children nodes attached to it. Ordinary binary trees allow nodes with any number of children at any point in the tree. They also place no restrictions on how the values stored in nodes that comprise a tree are arranged.
Data structures are most useful when they improve the speed with which data can be accessed by a computer, and modified versions of binary trees are used to improve their efficiency. A binary search tree is one in which all data values located on the left descending branch from a given node have values that are equal to or less than the value stored in that node. Values on the right side of a node in an ordered binary tree must, in turn, be greater than the value in the base node. This data ordering allows for a much more efficient search algorithm to be written.
The shape of a binary tree is also important in determining the efficiency of a search algorithm. The least efficient variety of a binary tree is one in which each node has only a single child. A computer may need to examine every item of data in the entire tree to locate a single piece of information in this configuration. The most efficient binary tree, in contrast, is one in which every node save for those at the bottom of the tree has two children and where all of the leaf nodes, the bottom nodes in the tree, are the same distance from the root.