A binary search tree (BST) is a tree-based data structure in which every node holds a key and has at most two children, arranged so that all keys in a node’s left subtree are smaller and all keys in its right subtree are larger than the node’s own key. Among data structures, this ordering property lets a program find, insert or delete a key by following a single path from the root, comparing at each step and discarding half of the remaining tree.
The efficiency of a binary search tree depends on its height. In a balanced tree with n keys, operations take time proportional to log n; in a degenerate tree that has become a chain, they degrade to time proportional to n. Self-balancing variants exist precisely to prevent that worst case.
How search, insertion and deletion work
Search starts at the root and compares the target with the current key. If they are equal, the search ends; if the target is smaller, it continues in the left subtree, otherwise in the right. Reaching an empty position means the key is absent. Insertion follows the same path and attaches the new node at the empty position where the search ended.
Deletion is the most involved operation and has three cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children is replaced by its in-order successor, the smallest key in its right subtree, or by its in-order predecessor, after which that successor is removed from its original position.
| Operation | Balanced tree | Degenerate tree |
|---|---|---|
| Search | O(log n) | O(n) |
| Insertion | O(log n) | O(n) |
| Deletion | O(log n) | O(n) |
| Minimum or maximum | O(log n) | O(n) |
| In-order traversal | O(n) | O(n) |
A tree of one million keys has a minimum height of about 20 levels, so a balanced search needs at most around 20 comparisons. If the same keys are inserted in already sorted order into a plain BST, every node gets only a right child and the tree becomes a linked list one million levels deep.
Ordered traversal and range queries
The defining advantage of a binary search tree over a hash table is that it keeps keys in sorted order. An in-order traversal, which visits the left subtree, then the node, then the right subtree, outputs all keys in ascending order in linear time without any separate sorting step.
| Traversal | Visit order | Typical use |
|---|---|---|
| In-order | Left, node, right | Listing keys in sorted order |
| Pre-order | Node, left, right | Copying or serializing the tree |
| Post-order | Left, right, node | Deleting the tree or freeing memory |
| Level-order | Level by level from the root | Visualizing structure, finding shallow nodes |
Ordering also enables range queries such as all keys between 100 and 200, and predecessor and successor queries such as the largest key smaller than a given value. In a balanced tree these run in O(log n + k) time, where k is the number of reported results.
Self-balancing variants
To guarantee logarithmic height, practical implementations use self-balancing binary search trees, which restructure themselves after insertions and deletions through local rotations that preserve the ordering property. They differ in how strictly they balance and how much work each update costs.
| Variant | Balancing rule | Typical strength |
|---|---|---|
| AVL tree | Subtree heights differ by at most one | Fastest lookups due to strict balance |
| Red-black tree | Color rules limit the longest path to twice the shortest | Fewer rotations per update, common in standard libraries |
| Splay tree | Recently accessed node moved to the root | Fast access to frequently used keys |
| Treap | Random priorities maintained as a heap | Simple code with expected balance |
| Scapegoat tree | Rebuilds subtrees that become too unbalanced | No extra data stored per node |
Red-black trees are the most widely deployed variant. They underlie ordered map and set types in several standard libraries, such as std::map in typical C++ implementations and TreeMap in Java, because their bounded rotation cost keeps updates predictable.
Binary search tree compared with other structures
Choosing a binary search tree is a trade-off between ordered operations and raw lookup speed. Neighboring data structures win in specific situations, and the table summarizes the most common alternatives.
| Structure | Lookup | Ordered operations | Best fit |
|---|---|---|---|
| Balanced BST | O(log n) | Yes, efficient | Dynamic sorted data with range queries |
| Hash table | O(1) on average | No | Exact-key lookup without ordering needs |
| Sorted array | O(log n) by binary search | Yes | Mostly static data, cache-friendly |
| Heap | Only the minimum or maximum | Partial | Priority queues |
| B-tree | O(log n) with few disk reads | Yes | Databases and file systems on storage |
A binary search tree must also be distinguished from a binary heap. Both are binary trees, but a heap orders each parent relative to its children only, which makes the minimum or maximum instantly available while arbitrary search remains linear.
Implementation pitfalls
- Inserting sorted input into an unbalanced BST silently produces a linear chain; use a self-balancing variant or shuffle the input.
- Duplicate keys need an explicit policy, such as rejecting them, storing a count or always placing equal keys on one side.
- Deep recursion in traversal can overflow the call stack on degenerate trees; iterative traversal avoids it.
- Mutating a key already stored in the tree breaks the ordering property; remove and reinsert instead.
- Poor cache locality: nodes scattered in memory make a BST slower in practice than its complexity suggests, compared with arrays.
For very large datasets on disk, the per-node cost of following pointers dominates, which is why databases use B-trees with many keys per node instead of binary trees.
The idea in brief
A binary search tree is a way of storing items so they can be found quickly by repeated halving. Think of a guessing game in which someone picks a number from 1 to 100. Each guess tells you whether to go higher or lower.
The tree is built so that smaller items always sit to the left and larger ones to the right. To find something, you just keep choosing left or right, and each choice rules out about half of what is left. Even among a million items, the answer is only about twenty steps away.
A practical scenario
A trading application keeps an order book for one stock, in which buy and sell orders are stored by price and constantly added, filled and canceled. The developers store each side of the book in a red-black tree keyed by price level, with every node holding the queue of orders at that price.
Finding the best bid or ask means reading the maximum or minimum key, and a new order at any price is inserted in logarithmic time. With about 5,000 active price levels, each update needs at most around 25 comparisons, and a range query lists all orders within a given band of prices for the depth display. A hash table would make exact-price lookups slightly faster but could not deliver this sorted view without re-sorting on every update.