Binary Search Tree

Where you meet BSTs in real systems

You rarely write a raw BST at work, but balanced search trees are everywhere underneath the tools you use. Here are three of them drawn out, the first with code you can run, then more examples.

Example 1: Order books on a stock exchange

An order book keeps bids and asks sorted by price so it can always match the best price first. New orders arrive and old ones are cancelled all day, so the structure needs fast inserts and deletes while staying sorted. Many implementations use an ordered map keyed by price. Open the example below to see the picture and the code.

from sortedcontainers import SortedDict  # pip install sortedcontainers


class OrderBook:
    """Price levels for one stock. Prices are whole cents, e.g. 10_050 = $100.50.

    Memory: O(n) for n price levels. Each side is kept sorted by price.
    SortedDict is not a tree, but it gives the same ordered operations.
    """

    def __init__(self):
        self.bids = SortedDict()  # price -> quantity buyers want
        self.asks = SortedDict()  # price -> quantity sellers offer

    def set_level(self, side, price, quantity):
        """Add, change or remove one price level. Quantity 0 removes it.

        Time: O(log n) to find the spot, whether the level is new or not.
        """
        if quantity == 0:
            side.pop(price, None)
        else:
            side[price] = quantity

    def best_bid(self):
        """Highest price a buyer will pay, or None. Time: O(log n)."""
        return self.bids.peekitem(-1) if self.bids else None   # last = largest

    def best_ask(self):
        """Lowest price a seller will accept, or None. Time: O(log n)."""
        return self.asks.peekitem(0) if self.asks else None    # first = smallest

Each version keeps buy prices and sell prices in two sorted maps. Setting a level to quantity 0 cancels it. The best bid is the largest buy price and the best ask is the smallest sell price. Every version was compiled and run on the same six price levels and printed the same best bid and ask before and after cancelling the top bid. Go and Python need a package (github.com/google/btree and sortedcontainers) because neither has a sorted map built in.

Example 2: Database indexes

When you run SELECT * FROM orders WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31', the database walks a B-tree index. A B-tree is like a BST where each node holds many keys and has many children. One node fills one disk page, so the database reads fewer pages per lookup. The ordering is what makes the range query fast: find the start, then read forward.

Example 3: The Linux CPU scheduler

Linux's Completely Fair Scheduler (CFS) kept runnable tasks in a red-black tree keyed by how much CPU time each had used. Picking the next task meant taking the leftmost node, the one that had run the least. Since Linux 6.6 the scheduler uses a newer algorithm called EEVDF, which also keeps its tasks in a balanced tree.

More real-world scenarios

4. Leaderboards and "rank between" queries

A game that needs "everyone with a score between 1,000 and 2,000" or "the three players just above me" needs ordered data that changes with every match. A hash map cannot answer these without scanning every player.

5. Java's HashMap, quietly

When many keys land in the same bucket of a Java HashMap, a bucket that grows past 8 entries is turned into a red-black tree. Lookups in that bucket then cost O(log n) instead of O(n), which protects the map from slow or malicious inputs.

6. File systems

Modern file systems such as Btrfs, XFS and NTFS keep directory entries and file extents in B-tree variants. Looking up one file name in a folder with a million files stays fast, and listing a folder comes out in sorted order.

7. Calendar and booking conflicts

"Is this meeting slot free?" means finding the nearest existing booking before and after the new start time. An ordered tree answers that in O(log n). A variation called an interval tree handles overlapping time ranges, as used by meeting-room and hotel booking systems.

8. Timers and scheduled jobs

A timer system needs "which job is due next, and what is due before now?" Keeping jobs in a tree ordered by due time gives you both answers, and cancelling a job is a normal delete. Some runtimes use heaps or timer wheels instead, which is a good example of picking by access pattern.

9. Memory management

Operating systems track which ranges of a program's memory are in use. Linux kept these ranges in a red-black tree so it could find "the range that contains this address" quickly. Newer kernels use a related structure called a maple tree for the same job.

10. Autocomplete and "nearest value" lookups

Pricing tables, tax brackets, shipping tiers and rate cards are all "find the largest threshold at or below this value". A sorted map's floor operation does that in one call, for example floorEntry in Java or lower_bound in C++.

Language standard libraries

Most languages already ship a sorted map or set. Check how yours works before writing your own.

The takeaway from the table: the languages that ship an ordered structure use a balanced tree for it. The ones that don't expect you to pull in a package, or to keep a sorted array and use binary search.

The takeaway

Whenever a system needs ordered data plus fast inserts, look for a balanced search tree. When it only needs exact-match lookups, it usually uses a hash map instead.