What is a Binary Search Tree

A binary search tree (BST) is a tree data structure where every node has at most two children, and a strict ordering rule holds: all values in the left subtree are less than the node, and all values in the right subtree are greater. This ordering is what makes searching fast.

How it works

To search for a value, start at the root. If the target is less than the current node, go left. If greater, go right. Repeat until you find the value or hit a null pointer (not found).

        8
       / \
      3   10
     / \    \
    1   6    14

Searching for 6: start at 8 (6 < 8, go left), arrive at 3 (6 > 3, go right), arrive at 6 (found). Three comparisons out of six nodes.

Insertion follows the same path — walk down the tree using the ordering rule until you find a null slot, then place the new node there. Deletion is more involved (especially when the node has two children) but follows similar logic.

When the tree is balanced — roughly the same depth on both sides — each comparison eliminates half the remaining nodes, giving O(log n) for search, insert, and delete. A tree with a million nodes needs only about 20 comparisons.

The danger is degeneration. If you insert already-sorted data (1, 2, 3, 4, 5...), each node becomes the right child of the previous one, forming a straight line — effectively a linked list with O(n) operations. Self-balancing variants (AVL trees, red-black trees) solve this by automatically restructuring after each insertion to maintain logarithmic height.

Why it matters

Binary search trees provide ordered storage with efficient lookup — something hash maps cannot do. When you need range queries ("find all values between 10 and 50"), sorted iteration, or finding the minimum/maximum, a BST is the right choice. They are also the conceptual foundation for B-trees, which generalize the idea to many keys per node and power database indexes worldwide.

See How Trees Work for the full progression from binary trees to B-trees.