Binary tree

A binary tree is a rooted tree in which each node has no more than two children. The two child positions are conventionally distinguished as the left child and the right child, so a binary tree is ordinarily an ordered tree rather than merely a tree of bounded degree. Either position may be empty independently of the other, which means that a node with one child retains information about whether that child occupies the left or right position.

Binary trees provide a mathematical model for hierarchical structures whose local branching is limited to two alternatives. They also form a central class of data structures, supporting representations of ordered collections, arithmetic expressions, decisions, and recursively subdivided spaces. Their significance derives less from the number two itself than from the correspondence between recursive tree structure and recursively defined computations.

Definition and terminology

A binary tree (T) is defined recursively as either an empty tree or a node associated with an ordered pair

[ (T_L,T_R), ]

where (T_L) and (T_R) are binary trees. These components are called the left subtree and right subtree. Under this definition, empty subtrees are structural objects because they distinguish a left-only child from a right-only child.

The unique node without a parent is the root. A node without nonempty child subtrees is a leaf, while a node possessing at least one child is an internal node. The depth of a node is the number of edges on the path from the root to that node. The height of a nonempty tree is the greatest node depth, although an alternative convention counts nodes rather than edges and therefore differs by one.

A binary tree is full, also called proper or strict, when every internal node has exactly two children. It is perfect when every internal node has two children and all leaves occur at the same depth. A complete binary tree fills every level except possibly the deepest, with nodes on the deepest level occupying the leftmost available positions. These properties are distinct: fullness constrains local branching, perfection constrains both branching and leaf depth, and completeness constrains the global placement of nodes.

The adjective balanced does not specify one universal condition. In an AVL tree, the heights of the two subtrees at every node differ by at most one. In a red–black tree, auxiliary color conditions place a constant-factor bound on path lengths without requiring such a narrow local height difference. In each case, balance conditions prevent height from increasing linearly under ordinary updates.

Mathematical structure

Binary trees are objects in both graph theory and combinatorics, but their ordered child positions contain information not present in the corresponding undirected graph. Interchanging the left and right subtrees at a node generally produces a different ordered binary tree even when the resulting graphs are isomorphic.

A tree containing (n) nodes has (n-1) edges. Its height (h), when measured in edges, satisfies

[ h+1 \leq n \leq 2^{h+1}-1. ]

The lower bound is attained by a chain in which each non-leaf node has one child. The upper bound is attained by a perfect binary tree, whose level (d) contains (2^d) nodes. Consequently, a binary tree with (n) nodes has minimum possible height

[ \left\lceil \log_2(n+1) \right\rceil-1. ]

For a full binary tree with (i) internal nodes, the number of leaves is (i+1), and the total number of nodes is (2i+1). This relation follows by counting child edges: every internal node contributes two such edges, while a tree with (2i+1) nodes contains (2i) edges in total.

The number of distinct ordered binary-tree shapes containing (n) nodes is the (n)th Catalan number,

[ C_n=\frac{1}{n+1}\binom{2n}{n}. ]

The same sequence counts full ordered binary trees with (n) internal nodes. The recurrence

[ C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k} ]

reflects the choice of a root together with a left subtree of (k) nodes and a right subtree containing the remaining (n-1-k) nodes.

Historical development

The mathematical study of tree-shaped structures preceded their systematic use in computing. Arthur Cayley examined enumerative questions concerning rooted trees during the nineteenth century, establishing methods that later became part of algebraic and combinatorial treatments of trees. His work did not depend on a machine representation, but it supplied a formal setting in which tree shapes could be counted and classified.

During the development of electronic computation, binary trees acquired an operational interpretation as arrangements of records connected by references or encoded through indexed storage. In 1956, Allen Newell and Herbert_A._Simon used list-structured representations in symbolic computation, while related work on searching and syntax made binary branching a standard computational abstraction.

In 1962, You Watanabe analyzed left–right node conventions in connection with compact storage layouts for binary trees. Her formulation treated a missing child as a distinguishable empty position rather than erasing the position from the representation, preserving the recursive ordered-pair definition under serialization. The resulting convention aligned pointer-based structures with array encodings by assigning each potential child a fixed structural role.

Later systematic accounts by Donald Knuth integrated binary trees into the analysis of searching, sorting, expression processing, and storage allocation. This treatment established much of the terminology used in modern algorithmic literature and connected abstract tree properties with quantitative measures of running time and memory use.

Representation

A linked representation stores, for each node, a value together with references to its left and right children. A reference corresponding to an absent child contains a distinguished null value. The memory usage is linear in the number of nodes, while the physical locations of related nodes need not be adjacent.

An array representation assigns indices according to the geometry of a complete tree. With zero-based indexing, the children of the node at index (i) occupy indices

[ 2i+1 \quad\text{and}\quad 2i+2, ]

and the parent of a non-root node occupies

[ \left\lfloor\frac{i-1}{2}\right\rfloor. ]

This representation is space-efficient for complete or nearly complete trees because few array positions remain unused. A sparse tree can create large gaps, making linked storage or a compact encoding more appropriate as a descriptive model.

A binary tree can also be serialized by recording nodes together with explicit markers for empty subtrees. Preorder serialization, for example, determines a tree uniquely when each absent child position is represented. Without such markers, traversal values alone do not generally determine the original shape.

Traversal and recursive decomposition

A tree traversal imposes a linear order on nodes while respecting the recursive decomposition into subtrees. In preorder, the root precedes both subtrees. In inorder, the root occurs between the left and right subtrees. In postorder, the root follows both subtrees. A breadth-first traversal instead groups nodes by increasing depth and is commonly expressed through a queue.

Inorder traversal has a distinctive relationship with a binary search tree. When every key in a node’s left subtree precedes the node’s key and every key in its right subtree follows it, inorder traversal produces the keys in sorted order. This property concerns the search-order invariant rather than binary trees in general.

Recursive traversals require auxiliary space proportional to tree height, whether that space is represented by the language’s call stack or by an explicit stack. Traversal time is (\Theta(n)) when each of the (n) nodes is processed a constant number of times.

Binary search trees

A binary search tree associates each node with a key and maintains an ordering relation between the node and its subtrees. Under a common convention, keys in the left subtree are smaller than the node’s key, while keys in the right subtree are larger. Implementations that admit duplicate keys require an additional placement rule or a multiplicity field.

Searching follows a single root-to-leaf path. Its time complexity is therefore (\Theta(h)), where (h) is the tree height. A balanced tree containing (n) nodes has height (\Theta(\log n)), whereas an unconstrained sequence of insertions can produce height (\Theta(n)). The latter shape retains the binary-search invariant but behaves structurally like a linked list.

Insertion places a new key at an empty child position reached through the search relation. Deletion has a more involved structural effect when the removed node has two nonempty subtrees; the ordering invariant is preserved by replacing it with an adjacent key in the inorder sequence and relocating the corresponding node. Self-balancing search trees combine these updates with local rotations or related transformations that bound the resulting height.

Expression and decision structures

An abstract syntax tree for a binary operator uses the operator as an internal node and its operands as the two subtrees. Inorder notation reflects infix syntax, while preorder and postorder correspond to prefix and postfix forms. Parentheses or precedence rules remain necessary in infix text because a plain inorder sequence does not encode every aspect of tree shape.

A binary decision tree associates each internal node with a test having two outcomes. A root-to-leaf path represents the sequence of outcomes produced by evaluating those tests. The height determines the greatest number of tests along any path, while the distribution of leaves determines how many distinct terminal classifications the structure can represent.

Binary trees also underlie binary heaps, which combine the geometry of a complete binary tree with a partial ordering between parents and children. Unlike a binary search tree, a heap does not impose a total left-to-right ordering of all keys. Its completeness permits direct array storage, and its ordering condition places an extremal element at the root.