A binary tree is a data structure made of nodes, where each node has at most two children, conventionally called the left child and the right child. One node is designated the root, and from it the structure branches downward; nodes with no children are called leaves. Because the two child positions are distinguished from each other, a left child and a right child are not interchangeable even when only one is present.
Donald Knuth treats trees, and binary trees in particular, as one of the foundational topics of information structures in The Art of Computer Programming, where the formal study of their properties and traversals is developed in detail. The binary tree’s regular shape makes it convenient both to reason about mathematically and to represent in memory, either with explicit child pointers or, in some cases, implicitly within an array.
A central operation on a binary tree is traversal, visiting every node in a systematic order. The three classic orders are pre-order (visit the node, then its left subtree, then its right subtree), in-order (left subtree, node, right subtree), and post-order (left subtree, right subtree, node). In-order traversal is especially important because, applied to an ordered binary tree, it visits the values in sorted sequence.
The binary tree is not a single algorithm but a shape that many structures build on. Binary search trees add an ordering invariant to support fast lookup, heaps add a different invariant to keep the smallest or largest element at the root, and expression trees use the structure to represent arithmetic with operators at internal nodes and operands at the leaves.