A binary tree is a tree data structure in which each node has at most two children, referred to as the left and right child. A binary search tree (BST) imposes an ordering constraint: every node in the left subtree holds a value less than the parent, and every node in the right subtree holds a value greater. This ordering makes searching, insertion, and deletion efficient, but in the worst case a BST degenerates into a linear chain. To prevent this, self-balancing variants such as the AVL tree and the red-black tree enforce structural invariants. An AVL tree requires that the difference between the heights of the left and right subtrees of any node is at most one. A red-black tree, by contrast, colors every node red or black and obeys five properties: every node is red or black, the root is black, every NULL leaf is black, red nodes have black children, and every path from a node to its descendant leaves contains the same number of black nodes. Other advanced BST variants include the splay tree, which moves recently accessed elements to the root through a splaying step, and the treap, which combines a BST property on keys with a heap property on randomly assigned priorities.
Beyond search trees, several specialized tree structures serve other needs. A heap is a complete binary tree used as a priority container, with the min-heap and max-heap variants enforcing parent-child ordering by value. A B-tree is a self-balancing, generalized search tree in which each internal node may have more than two children, allowing it to maintain sorted data and provide logarithmic-time searches, sequential access, insertions, and deletions, which is why it is widely used in databases and filesystems. A B+ tree refines this design by storing all data in the leaf nodes and using internal nodes purely for indexing, with leaves typically linked for fast sequential access. A trie, also called a digital or prefix tree, is a search tree used for locating keys, especially strings, by traversing character by character along the path determined by each digit or letter.
Many other tree structures target specific query patterns. A segment tree stores information about intervals or segments, allowing range queries such as which stored segments contain a given point to be answered efficiently. A Fenwick tree, also called a binary indexed tree, supports efficient element updates and prefix-sum queries in a table of numbers. Spatial data is often organized using a quadtree, which recursively subdivides a two-dimensional space into four quadrants, an octree, which does the same for three-dimensional space using eight octants, an R-tree, which indexes multi-dimensional information such as geographical coordinates, rectangles, or polygons, or a k-d tree, a space-partitioning binary search tree for points in a k-dimensional space. Less common but still important structures include the expression tree, which represents expressions with operands as leaves and operators as internal nodes; the Cartesian tree, which is heap-ordered with an in-order traversal matching the original sequence; the threaded binary tree, which uses empty child pointers to speed up in-order traversal without recursion or a stack; the Van Emde Boas tree, which implements an associative array with integer keys and runs all operations in \(O(\log \log M)\) time, where M is the universe size; the rope, which efficiently stores and manipulates very long strings; the persistent data structure, which preserves previous versions of itself when modified; and the Judy array, a fast cache-friendly associative array for integers or strings. To walk through any of these structures, four standard binary tree traversals are available: inorder (Left, Root, Right), preorder (Root, Left, Right), postorder (Left, Right, Root), and level order, which is simply a breadth-first traversal of the tree.