Data Structure

Binary Search Tree

A tree where every node's left side holds smaller values and its right side larger ones. Searching, inserting, and deleting each walk a single path from the root, so a well-balanced tree of a million values is only about 20 levels deep — and reading it in order gives you the values sorted.

SearchO(log n)
InsertO(log n)
Worst caseO(n)
In-orderSorted

Try It — Animated Flow

20
30
40
50
60
70
80
Every node's left subtree holds smaller values and its right subtree larger ones. Pick an operation and press Run.
Step 1 / 1
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

Sorted maps and sets
Java's TreeMap/TreeSet and C++'s std::map are self-balancing BSTs (red-black trees), so every operation stays O(log n).
Database indexes
B-trees, the wide and shallow cousins of BSTs, power nearly every SQL index.
Range queries
“Every booking between 9am and 5pm”: walk to the start, then read in order. A hash table can't do this.
Leaderboards and schedulers
Keep scores or timers ordered as they change, with quick access to the smallest and largest.

Trade-offs

Reach for a BST when
  • Data must stay sorted while you insert and delete
  • You need ranges, or the nearest, smallest, or largest value
  • In production, use a self-balancing one (TreeMap, std::map)
Avoid it when
  • Values arrive sorted and the tree doesn't rebalance (try Reset → Skewed)
  • You only look up exact keys: a hash table is O(1)
  • The data is small and static: a sorted array plus binary search is simpler