A binary search tree, or BST, is a node-based structure where every node has at most two children, and a strict ordering rule holds at every node: everything in the left subtree is smaller, everything in the right subtree is larger. That single invariant is what lets a balanced tree search, insert, and delete in O(log n) time — the same logarithmic behavior as binary search on a sorted array, but with cheap insertion and deletion that a sorted array cannot offer. It is easy to confuse a binary search tree with the binary search algorithm; the algorithm operates on a sorted array, while the tree is a distinct structure that happens to support a similar search strategy.
What changed in 2026
- Self-balancing variants remain the production default. Plain BSTs are still taught first because they are simple to reason about, but AVL trees, red-black trees, and B-trees for on-disk structures are what production databases and language standard libraries actually ship.
- Language standard libraries lean on balanced trees under the hood. Java TreeMap, C++ std::map, and similar ordered-map types are red-black trees, so most developers use a self-balancing BST daily without building one by hand.
- Interview emphasis shifted slightly toward correctness over raw implementation. Recognizing when a BST is the wrong tool, versus hand-rolling one under time pressure, carries more weight than it used to.
The node structure and the ordering invariant
Each node stores a value and two child pointers:
Node:
value
left -> Node or null
right -> Node or null
Invariant at every node N:
all values in N.left < N.value
all values in N.right > N.value
This invariant is recursive — it holds at the root and at every subtree — which is what turns search into a repeated go-left-or-go-right decision.
Core operations
- Search: compare the target to the current node; go left if smaller, right if larger, repeat until found or a null pointer is reached. O(h), where h is the tree height.
- Insert: search for where the value belongs, then attach a new node at the null pointer reached along the way. O(h).
- Delete: the tricky one. 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 value in its right subtree, which is then deleted from its original spot.
- In-order traversal, meaning left, node, right, visits every value in sorted order — a useful property no hash table offers.
Why balance matters
The O(log n) claim depends entirely on the tree being roughly balanced, meaning height h is close to log n. Insert values in sorted order into a plain BST with no rebalancing, and it degenerates into a straight chain — effectively an array-adjacent linked list — with O(n) search, insert, and delete. Self-balancing trees such as AVL and red-black trees solve this by rotating nodes during insertion and deletion to keep height logarithmic no matter the insertion order.
BST vs the alternatives
| Structure |
Search |
Insert |
Ordered iteration |
Notes |
| Sorted array |
O(log n) |
O(n) |
Yes |
Fast search, expensive insert |
| Unbalanced BST |
O(n) worst case |
O(n) worst case |
Yes |
Degenerates on sorted input |
| Balanced BST, AVL or red-black |
O(log n) |
O(log n) |
Yes |
Best all-round ordered structure |
| Hash table |
O(1) average |
O(1) average |
No |
Faster, but no ordering |
Common pitfalls
Building an unbalanced BST from already-sorted data. This is the classic trap — it silently turns every operation into O(n). When insertion order is not random, use a self-balancing variant or bulk-build from the sorted array instead.
Reaching for a BST when ordering is not needed. If the code never iterates in sorted order and never needs range queries between X and Y, a hash table is faster for search and insert. A BST earns its keep specifically through ordered operations.
Hand-rolling deletion incorrectly. The two-children case is where most bugs live. Always replace with the in-order successor or predecessor and delete that node from its original location — swapping values alone is not enough.
FAQ
Is a binary search tree the same as the binary search algorithm?
No. Binary search is an algorithm for finding a value in a sorted array. A binary search tree is a data structure with nodes and pointers. They share the same halve-the-search-space idea but are not interchangeable.
What is the difference between a BST and a heap?
A heap only guarantees a parent is smaller, or larger, than its children — it is not fully ordered and does not support efficient in-order traversal or search for an arbitrary value. A BST maintains a full ordering that supports search, range queries, and sorted iteration.
Is implementing a self-balancing BST from scratch necessary?
Almost never in application code — the built-in ordered map or set in most languages, such as TreeMap, std::map, or SortedDict, is already a balanced tree.
Where to go next