prime · Apr 17, 2026 · 2 min read

BST (Binary Search Tree)

A Binary Search Tree (BST) is a Tree where every node follows one rule: all values in its left subtree are smaller than the node, and all values in its right subtree are larger ^[1]. This rule means you can always find a value by making a simple left/right decision at each level, cutting the search space in half each time, giving you O(log n) performance when the tree is balanced.

        [50]
       /    \
    [20]    [80]
    /  \    /  \
  [10][30][60][90]

Search for 60: 50 → go right → 80 → go left → 60. Found in 3 steps.

The balancing problem

A BST works well only when it stays balanced (roughly equal height on both sides). The problem is that a naive BST does not stay balanced on its own. If you insert data in sorted order like 10, 20, 30, 40, 50, the tree becomes a straight line to the right:

10
  \
  20
    \
    30
      \
      40   ← this is now O(n), as slow as a simple scan

This is called a degenerate tree or a skewed tree. It completely kills performance.

Rotations: how BSTs fix imbalance

To fix skewed trees, self-balancing BST variants (like AVL trees and Red-Black trees) use rotations: operations that restructure the tree to reduce height while keeping the BST property intact.

A right rotation on a node pulls its left child up to take its place:

Before:          After right rotation on [30]:
  [30]                [20]
  /                  /    \
[20]              [10]    [30]
/
[10]

A left rotation does the opposite: pulls the right child up.

In practice, self-balancing BSTs apply rotations automatically after every insert or delete to keep the tree balanced. This works, but it is complex to implement and adds overhead — especially bad when the tree lives on disk, because a rotation might mean updating many disk pages.

This is exactly why B-tree was invented. B-trees avoid rotations entirely by using wide nodes (many keys per node) and only splitting/merging when needed, which is much friendlier to disk I/O.

BST vs B-tree for databases

BSTs are very useful in memory (many in-memory data structures use Red-Black trees internally, like Java's TreeMap). But for disk-based databases, the B-tree is the standard because it is designed around the realities of disk I/O.

Sources

1. Binary search tree — Wikipedia