Binary Search Trees Explained: How They Work

A binary search tree (BST) is a data structure that stores values in nodes arranged so that, for every node, everything in its left subtree is smaller and everything in its right subtree is larger. That single invariant is what makes lookup, insertion, and deletion all run in roughly logarithmic time on a balanced tree — instead of scanning a whole list, you eliminate half the remaining candidates at every step.

The core invariant

Every node in a BST has at most two children — commonly called left and right — and the ordering rule applies recursively at every level: a node’s left subtree contains only smaller values, its right subtree contains only larger values, and both subtrees are themselves valid binary search trees. There are no duplicate values in the simplest form of the structure, though real implementations often handle duplicates with a count or a tie-breaking rule.

This is the same principle behind binary search on a sorted array, but represented as a tree instead of a flat list — which is what lets you insert and delete without shifting every other element, something a sorted array can’t do cheaply.

Lookup and insertion

Searching for a value starts at the root and compares the target to the current node. If it’s smaller, move left; if larger, move right; if equal, you’ve found it. Each comparison discards an entire subtree from consideration, so a lookup takes a number of steps proportional to the tree’s height rather than its total size.

Insertion follows the same path a lookup for that value would take, and attaches the new node as a leaf at the point where the search would have failed. Deletion is the trickiest of the three operations: removing a leaf is trivial, removing a node with one child just splices the child up, but removing a node with two children requires finding its in-order successor (the smallest value in its right subtree) to replace it, so the tree’s ordering invariant stays intact.

Traversal orders

Visiting every node in a BST can be done in a few standard orders, each useful for a different purpose:

• In-order (left, node, right) — visits nodes in ascending sorted order. This is the traversal you’d use to print all values sorted.
• Pre-order (node, left, right) — visits the root before its subtrees, useful for copying or serializing a tree’s structure.
• Post-order (left, right, node) — visits children before their parent, useful for safely deleting a tree bottom-up.

All three are typically implemented recursively, and all run in time proportional to the number of nodes since each node is visited exactly once.

Why balance matters

The catch with a plain BST is that its performance depends entirely on its shape, and shape depends on insertion order. Insert values in already-sorted order and every node ends up with only one child, degrading the tree into what’s effectively a linked list — lookups become O(n) instead of the O(log n) a balanced tree provides. See Big O notation for how that gap plays out as data grows.

Self-balancing trees — AVL trees and red-black trees are the two most common — solve this by performing rotations during insertion and deletion that keep the tree’s height close to the theoretical minimum, guaranteeing O(log n) operations regardless of insertion order. Red-black trees are the more common choice in practice (they back the ordered map/set implementations in several standard libraries) because they require fewer rotations on average than AVL trees, at the cost of being slightly less tightly balanced.

BSTs vs hash tables

Both structures support fast lookup, but they trade off different things. A hash table gives O(1) average-case lookup and insertion with no ordering guarantee — you can’t cheaply ask for “the next smallest key” or iterate in sorted order. A balanced BST gives O(log n) operations, slower on average than a hash table, but keeps data in sorted order at all times, supports efficient range queries, and doesn’t depend on a good hash function to avoid worst-case collisions.

That ordering property is exactly why BST-derived structures (specifically B-trees, a wider, shallower generalization) are the standard choice behind database indexes: a database frequently needs range queries like “all rows where price is between X and Y,” which a sorted tree structure supports directly and a hash-based index cannot.

Where BSTs show up in practice

Beyond textbook examples, BST-family structures underlie ordered maps and sets in most standard libraries, the indexes inside relational databases, and any application that needs fast lookup alongside sorted iteration or range queries — a priority queue for a task scheduler, a leaderboard, or an interval-overlap check are all natural fits.

The takeaway

A binary search tree keeps every node’s left subtree smaller and right subtree larger, which turns lookup, insertion, and deletion into operations proportional to the tree’s height rather than its size. That guarantee only holds if the tree stays balanced — an unlucky insertion order can degrade a plain BST to linked-list performance, which is why real systems use self-balancing variants like red-black trees, or the wider B-trees that power database indexes.