A binary tree is a tree in which every node has at most two children, conventionally designated the left child and right child. In computer science, it is a fundamental data structure for representing hierarchical relationships and organizing computation. The distinction between left and right matters: a node with only a left child generally represents a different structure from a node with only a right child.
Binary trees underpin ordered dictionaries, priority queues, expression evaluation, compression codes, and many recursive algorithms. Their usefulness comes from combining a simple local structure with potentially efficient global organization. A well-balanced binary tree can connect a root to any of its nodes through only logarithmically many links, whereas a poorly shaped tree can become a linear chain. The term describes a structural form, not a particular ordering rule: binary search trees, binary heaps, and expression trees impose different meanings and constraints on the same basic arrangement.
Definition and structural terminology
A binary tree can be defined recursively as either an empty tree or a node associated with two binary trees, its left and right subtrees. This definition makes empty child positions explicit. A nonempty tree has one distinguished root, and every other node has exactly one parent. Following child links cannot lead back to an earlier node, and every node is reachable from the root. Thus, an arbitrary graph whose vertices each have two outgoing links is not necessarily a binary tree: cycles and shared children violate the ordinary tree model.
The recursive definition directly supports recursive procedures. To compute the number of nodes, for example, a procedure returns zero for an empty tree and otherwise adds one to the sizes of the two subtrees. Inductive proofs have the same form: establish a claim for the empty tree, then show that it holds for a node whenever it holds for both child subtrees. This correspondence between structure, algorithms, and proofs makes binary trees a standard example in formal verification.
A leaf is a node with no children; an internal node has at least one child. A node’s depth is the number of edges from the root to that node, so the root has depth zero. Its height is the largest number of edges on a downward path from that node to a leaf. Under this convention, a leaf has height zero and the height of an empty tree is often defined as . Some texts count nodes rather than edges when measuring height, so formulas must be interpreted with their convention in mind.
A path is a sequence of adjacent nodes linked through parent–child relationships. Ancestors lie on a node’s path from the root, while descendants lie below it. A subtree rooted at a node includes that node and all its descendants. Subtrees are not arbitrary selections of nodes: omitting a descendant generally destroys the intended rooted-subtree interpretation.
Binary trees are usually ordered, meaning that the two child positions are distinguished. This differs from an unordered rooted tree with at most two children, in which exchanging two children does not change the structure. It also differs from the left-child, right-sibling representation of a general tree. In that encoding, one link identifies the first child and the other identifies the next sibling; the resulting binary structure represents a hierarchy whose original nodes may have any number of children.
Shapes, height bounds, and enumeration
Several shape classifications describe binary trees independently of the values stored in them. A full, proper, or strict binary tree is one in which every node has either zero or two children. A perfect binary tree has two children at every internal node and all leaves at the same depth. A complete binary tree has every level filled except possibly the last, whose nodes occupy the leftmost available positions. These terms are not interchangeable, although terminology varies between publications.
With root depth zero, a binary tree has at most nodes at depth . A tree of height therefore contains at most
nodes, with equality precisely for a perfect tree. Consequently, the height of any nonempty binary tree with nodes satisfies
The upper bound occurs when every internal node has exactly one child, producing a chain. A complete tree has height . These bounds explain why shape is central to the time complexity of operations that follow one root-to-leaf path.
Useful counting identities follow from the fact that a nonempty tree with nodes has edges. Let denote the numbers of nodes with zero, one, and two children. Counting edges through their parent nodes gives
and hence . A full binary tree with internal nodes therefore has leaves and total nodes. Similarly, if each node provides two child-pointer positions, exactly of the tree’s positions are empty.
The number of distinct ordered binary-tree shapes with nodes is the th Catalan number:
The recursive decomposition at the root yields
Here, nodes belong to the left subtree and to the right. The first values are , including the empty tree.
The asymptotic estimate also has a storage implication: distinguishing all ordered binary-tree shapes requires approximately bits, apart from lower-order terms. This is a bound on encoding shape alone; labels, stored records, and navigation support require additional information. It motivates succinct representations that approach this bound while still permitting useful tree operations.
Memory representations and storage layouts
The most direct representation stores each node as a record containing a value and two references. An optional parent reference supports upward navigation, while auxiliary fields may store subtree size, height, color, or other information. In the C programming language, child references are commonly pointers; in managed languages, they are object references. A missing child is usually represented by a null reference or by a designated sentinel node.
Linked representations accommodate arbitrary shapes and local structural changes. Connecting or disconnecting a known subtree may require changing only a few references. Their costs include per-node reference storage, allocation overhead, and potentially poor spatial locality. Nodes allocated at different times may occupy distant memory locations, so following a search path can cause several cache misses. An operation with fewer comparisons is therefore not necessarily faster than an array-based alternative.
Complete trees admit a particularly compact array representation. With zero-based indexing, the children of the node at index occupy
when those indices are below the array length. For , the parent index is
No explicit child pointers are needed. This representation is especially effective for binary heaps because completeness guarantees that all occupied positions form a contiguous array prefix. For an arbitrary sparse tree, however, assigning positions by the same formulas can waste enormous space: a long rightward chain reaches exponentially increasing indices.
A threaded binary tree reuses some otherwise empty child links to identify a node’s predecessor or successor in a traversal order, usually inorder. Tags distinguish threads from genuine child links. Threading can allow traversal without a recursion stack, although insertion and deletion must preserve both structural links and threads. Parent pointers offer another way to navigate without an explicit traversal stack, at the cost of an extra reference per node.
Storage design also affects whether trees can be shared or preserved across updates. A persistent data structure retains access to earlier versions. In an immutable binary search tree, an update can copy only the nodes on the affected search path and reuse all untouched subtrees. This costs new nodes for height , rather than copying the entire tree. The combined representation of several versions contains shared subtrees, so it is a directed acyclic graph even though each individual version has tree structure.
Serialization must preserve both node contents and shape. A preorder sequence with explicit markers for empty children is sufficient, while a preorder list of values alone generally is not. This distinction is important when exchanging trees between programs: traversal order by itself does not always encode missing child positions.
Traversal and recursive computation
A tree traversal visits the nodes in a specified order. The three standard depth-first orders differ in when they process the root relative to its subtrees. Preorder visits root, left subtree, then right subtree. Inorder visits left subtree, root, then right subtree. Postorder visits left subtree, right subtree, then root. For a root labeled , with leaf children and , these orders produce , , and , respectively.
Each order serves a different dependency pattern. Preorder processes a node before its descendants, making it useful for top-down copying and certain serialized encodings. Postorder processes children before their parent, supporting expression evaluation, subtree aggregation, and deletion of dynamically allocated trees. Inorder is especially important for binary search trees because it lists their keys in sorted order. That sortedness results from the search-tree ordering invariant, not from inorder traversal alone.
A recursive traversal takes time for nodes, assuming constant work per visit. Its auxiliary call-stack requirement is , where is the height. This becomes for a balanced tree but for a chain. An iterative traversal can replace language-level recursion with an explicit stack, but this does not automatically improve the asymptotic space bound. It mainly gives the implementation direct control over stack storage and failure handling.
Breadth-first, or level-order, traversal visits nodes by increasing depth, normally using a queue. Its auxiliary storage is proportional to the maximum width of the tree, which can be . Depth-first and breadth-first traversal therefore have different memory profiles: a broad, shallow tree can require a large breadth-first queue but only a short depth-first stack.
For distinct node labels, preorder together with inorder uniquely determines a binary tree; postorder together with inorder does as well. The inorder sequence identifies the nodes belonging to each subtree, while preorder or postorder identifies the root at each recursive step. Preorder and postorder alone do not generally determine the tree, because they cannot distinguish a single left child from a single right child. Additional shape restrictions can remove this ambiguity.
Many tree algorithms are postorder computations rather than simple listings. Subtree size, height, and balance can each be computed from the corresponding child results. For example,
Such recurrences are elementary examples of dynamic programming on trees: each subtree produces information used by its parent. Combining height computation with balance checking in one pass takes time; repeatedly recomputing subtree heights at every node can instead take on unfavorable shapes.
Binary search trees and ordered operations
A binary search tree adds a key-ordering invariant to the binary-tree structure. In the simplest version with distinct keys, every key in a node’s left subtree is smaller than that node’s key, and every key in its right subtree is larger. This condition applies to whole subtrees, not merely to immediate children. Implementations that permit duplicate keys require an explicit policy, such as storing a multiplicity count or ordering records by a key–identifier pair.
Search starts at the root and compares the target with the current key. Equality ends the search; a smaller target leads left and a larger target leads right. Reaching an empty child position establishes absence. The procedure resembles binary search in a sorted array, but the split sizes depend on tree shape rather than automatically dividing the remaining candidates approximately in half. Searching costs , not unconditionally .
Insertion first follows a search path and places a new node at the appropriate empty child position. Without balancing, insertion order can determine performance dramatically. Inserting produces a rightward chain and requires quadratic total time. Under the different assumption that distinct keys arrive in a uniformly random permutation, expected search costs are logarithmic. This average-case statement does not protect an ordinary tree from adversarial or highly structured input.
Deletion has three structural cases. A leaf can simply be removed. A node with one child can be replaced by that child. A node with two children is commonly replaced, in key or structural position, by its inorder successor—the minimum node in its right subtree—or by its inorder predecessor. That successor has no left child, so removing it reduces to a simpler case. Whether an implementation moves records or relinks nodes can matter when external references identify particular node objects.
Ordered trees support operations beyond exact lookup. The minimum is found by following left links; the maximum by following right links. A lower-bound query finds the smallest key not less than a target. A range-reporting traversal can output qualifying keys in time by avoiding subtrees that lie entirely outside the requested interval.
Augmentation extends these capabilities. If each node stores its subtree size, an order-statistic tree can find the key of a given rank or count keys below a target in time. Such fields must be updated whenever the structure changes. The method illustrates a general principle: binary-tree topology determines navigation, while carefully maintained local summaries can support richer queries without changing the basic ordering rule.
Balancing, rotations, and performance guarantees
A balanced search tree maintains structural constraints that keep height logarithmic in the number of nodes. “Balanced” does not normally mean that every pair of subtrees has exactly the same size or height. Different tree families enforce different local invariants, chosen to balance search depth, update cost, metadata, and implementation complexity. Their common purpose is to prevent the linear chains possible in an unrestricted search tree.
The fundamental restructuring operation is a rotation. In a right rotation, a node with left child moves below ; ’s former right subtree becomes ’s left subtree. If the relevant subtrees are , their inorder sequence remains . Thus a rotation changes shape without changing the ordering of keys. A constant number of references changes, although parent links and augmented fields must also be repaired.
An AVL tree, introduced by Georgy Adelson-Velsky and Evgenii Landis in 1962, requires the heights of each node’s two child subtrees to differ by at most one. A node stores enough information to detect imbalance, commonly height or a balance factor. Insertions and deletions update information along an ancestor path and use single or double rotations where necessary. The minimum node count for a given height follows a Fibonacci-like recurrence, establishing a height bound of approximately .
A red–black tree uses a different invariant. Nodes are colored red or black; red nodes cannot have red children, and all paths from a node to its descendant empty leaves contain the same number of black nodes. Under the usual convention that the root and empty leaves are black, these rules bound height by . Recoloring and rotations restore the invariants after updates. The looser height constraint can offer a different trade-off between search depth and restructuring work.
Other families obtain logarithmic guarantees through different mechanisms. A splay tree moves an accessed node toward the root through rotations. A single operation can take linear time, but sequences of standard operations have logarithmic amortized cost. A treap combines search-tree order on keys with heap order on independently randomized priorities. Its expected logarithmic height follows from a distribution equivalent to that of a randomly built search tree, assuming an appropriate priority model.
These guarantees describe different forms of computational complexity. Worst-case bounds constrain each operation, amortized bounds constrain a sequence’s total cost, and expected bounds depend on randomness. They should not be conflated. Nor does a tighter mathematical height bound alone establish superior practical performance: allocation, cache behavior, comparison cost, and workload locality can dominate small differences in path length.
Binary heaps and priority queues
A binary heap combines a complete binary-tree shape with a local ordering rule. In a min-heap, every parent key is no greater than either child key; in a max-heap, every parent key is no less. The minimum or maximum is therefore at the root. Unlike a search tree, a heap imposes no general ordering between the left and right subtrees, so locating an arbitrary key may require examining all nodes.
The completeness constraint makes a binary heap a natural array-based implementation of a priority queue. The root occupies the first array position, and child and parent positions follow simple index formulas. Accessing the highest-priority element takes time. Insertion appends a value at the next open position, then repeatedly exchanges or moves it upward until heap order is restored. Because a complete tree has logarithmic height, this sift-up procedure takes time.
Removing the root replaces it with the final array element and shortens the array. The replacement is then moved downward, each time choosing the child that should precede it in heap order. This sift-down operation also takes . Updating a known element’s priority can move it either upward or downward. If the priority-queue interface identifies elements by external handles, an additional mapping from handles to current array indices is usually needed.
Constructing a heap does not require inserting every element separately. Bottom-up heap construction starts at the final internal node and sifts downward in reverse level order. Its total cost is , because most nodes are near the leaves and can move only a short distance. A standard bound uses the convergent series
which bounds the average amount of downward work per node up to constant factors. This is a prominent example of an algorithm whose total cost is smaller than multiplying the worst single-step cost by the number of steps.
Heapsort builds a max-heap and repeatedly moves its maximum into the unfilled end of an array. It has worst-case running time and can operate in place, though its usual implementation is not stable. Binary heaps also appear in event simulation and graph algorithms such as Dijkstra’s algorithm, where extracting the smallest tentative distance is a central operation.
A heap’s completeness balances its shape without rotations or explicit balance metadata. That convenience comes with a narrower query repertoire: efficient priority access does not imply efficient predecessor search, sorted iteration, or range reporting. Heap order and search-tree order serve different interfaces despite sharing binary-tree terminology.
Expression processing, coding, and specialized trees
Expression trees use topology to encode computation. An internal node may represent an operator and its children the operands; leaves represent constants or variables. For the expression , the root is multiplication, its left child is addition, and its right child is . Postorder traversal yields a natural evaluation order, while preorder and postorder correspond to familiar prefix and postfix notations.
In a compiler, an abstract syntax tree captures grammatical structure without retaining every punctuation token. Binary operators naturally form binary nodes, but a complete syntax tree need not be binary: function calls can have many arguments, and statement blocks can contain many statements. Unary operators also require a defined convention for their single operand. Converting expressions into binary structure therefore depends on the language’s syntax and representation choices, not merely on drawing branches.
Huffman coding, introduced by David Huffman in 1952, constructs a binary tree for a prefix code. Symbols occupy leaves, and left and right edges receive the labels 0 and 1. A symbol’s codeword is the root-to-leaf bit sequence. Because no symbol is placed at an ancestor of another symbol, no codeword is a prefix of another. The algorithm repeatedly joins the two least-weight trees, producing an optimal binary prefix code for given symbol weights under its standard assumptions.
A segment tree organizes an indexed sequence into recursively divided intervals. Internal nodes store combinations such as sums, minima, or maxima. With a suitable associative operation, point updates and interval queries take time, and storage is . The binary hierarchy makes it possible to cover a query interval with a small number of stored segments rather than inspecting every element. Related structures, such as the Fenwick tree, encode different hierarchies implicitly and should not be identified with ordinary pointer-based binary trees.
Binary decision trees represent successive two-way tests. In decision-tree learning, an internal node may test whether a feature falls below a threshold, while leaves store predicted classes or numerical values. Tree depth measures the number of tests along a prediction path. Branch meanings differ from search-tree ordering: two branches partition observations according to a test, rather than necessarily placing smaller and larger stored keys on opposite sides.
A Merkle tree combines child hashes recursively, committing to many data items through a root hash. Binary forms are common, although the broader concept permits other branching factors. A proof for one leaf contains the sibling hashes needed to reconstruct the root, giving logarithmic proof size in a balanced binary tree. These uses illustrate how the same topology can organize syntax, probabilities, intervals, decisions, or cryptographic commitments while assigning completely different semantics to its nodes and edges.
Historical development and implementation context
Binary trees emerged from overlapping traditions in mathematical enumeration, symbolic representation, and automatic computation rather than from one isolated invention. Catalan’s nineteenth-century work belongs to the mathematical background of counting parenthesizations and related tree structures. In twentieth-century computing, hierarchical expressions and decision procedures made binary branching an increasingly practical representation, especially as machines gained facilities for manipulating linked records.
Several developments established distinct algorithmic roles during the 1950s and 1960s. Huffman’s 1952 coding method made weighted binary trees central to lossless compression. John McCarthy’s 1960 account of Lisp described recursive symbolic computation using list structures built from pairs. Such pair-based representations are closely related to binary branching, although unrestricted shared or cyclic pair structures are not necessarily trees. The AVL tree followed in 1962, providing a systematic answer to the degeneration of ordinary search trees.
Priority queues developed along a separate path. J. W. J. Williams introduced heapsort in 1964, and Robert Floyd’s work that year established the efficient bottom-up heap-construction approach. Rudolf Bayer introduced symmetric binary B-trees in 1972, and Leonidas Guibas and Robert Sedgewick developed the red–black formulation in 1978. Daniel Sleator and Robert Tarjan introduced splay trees in 1985, emphasizing amortized analysis rather than a rigid balance condition.
The widening gap between processor speed and memory-access cost also influenced where binary trees were used. For storage systems, a B-tree groups many keys and children into each node, reducing the number of page accesses compared with a binary search tree holding one key per node. B-trees were introduced by Rudolf Bayer and Edward McCreight in 1970 and became important in database indexes and file organization. Their role shows why a logarithmic height bound alone is insufficient when each navigation step may require a disk or page access.
Modern implementation concerns include ownership, iterator behavior, and concurrency. A rotation is locally simple in a sequential program but can expose inconsistent links to another thread unless synchronization is designed around it. Removing nodes also raises memory-reclamation questions: another reader may still hold a reference to a node that has been detached. Garbage collection, locks, and specialized reclamation schemes address different parts of this problem.
Testing and verification focus on invariants rather than appearance. A search tree must satisfy global key bounds; a heap must satisfy both shape and parent–child order; an augmented tree must maintain correct summaries after every update. A tree can look balanced in a diagram yet contain a misplaced descendant, and a locally correct rotation can still leave stale parent references or subtree sizes. These implementation obligations distinguish the mathematical simplicity of binary trees from the care required to maintain them in production software.