Skip to content
Hari KharelStudy

Binary search trees / ordered maps

intermediateCommon atGoogleMetaAmazonJane StreetStripeRead firstBinary treesBinary searchPractise in the Sandbox →

A binary search tree keeps one rule at every node: keys in the left subtree are smaller, keys in the right subtree are bigger. Every operation walks a single root-to-leaf path, so it costs O(h), the tree’s height. A plain BST can degrade to a chain (h = n) on sorted input; a self-balancing tree (AVL, red-black) guarantees h = O(log n). That balanced tree is what an ordered map is: a hash map that also knows “smallest”, “next bigger” and “everything between a and b”.

The idea in plain words

Section titled “The idea in plain words”

A BST is binary search, frozen into a tree. In a sorted array you look at the middle and throw away half. In a BST the root is the middle: everything smaller is to its left, everything bigger to its right. Each comparison throws away a whole subtree.

The array version is fast to search but slow to change: inserting in the middle shifts everything after it. The tree version only has to hang a new leaf, so it’s fast to change too. You get both, as long as the tree stays bushy.

That “as long as” is the whole story of BSTs:

  • Insert keys in random order and the tree is usually bushy: height about 3·log₂ n in the worst path.
  • Insert them in sorted order and every key goes right of the previous one. The “tree” is a linked list, and every operation is O(n).
  • Self-balancing trees fix this by doing small local repairs (rotations) after inserts and deletes, so the height stays O(log n) no matter the order.

See it

Section titled “See it”

Search, insert and delete keys. Then press sorted to load 12 keys in order and watch the tree collapse into a chain, and middle-first to load the same keys so it stays perfectly balanced. The log underneath shows how many comparisons each operation cost.

BST sandbox: search, insert, delete
interactive
operate
load 12 keys
2035403060807050
keys8
height3
best possible3
worst-case search4 comparisons
comparingpath takenresultsuccessorbeing deleted
Every key in a left subtree is smaller than its ancestor; every key in a right subtree is bigger. Search, insert or delete a key.
1 / 1
Operation log
Try: delete 30 (two children), then load the sorted keys and search for 60.

Things to try:

  • Delete 30: it has two children, so its successor (35, the smallest key bigger than 30) takes its place.
  • Delete 20, a leaf, then 40, which now has a single child.
  • Load sorted, then search for 60. Count the comparisons. Load middle-first and search again.

When to reach for it

Section titled “When to reach for it”
The problem says… Why an ordered map / BST fits
“the next larger / previous smaller key”, “closest value to x” Floor and ceiling are O(log n) walks. A hash map can’t do this without scanning.
“all keys between a and b”, “count in a range” Find a, then walk in order until b: O(log n + k).
“keep it sorted while items arrive and leave” Insert and delete are O(log n). A sorted array is O(n) per change; a heap can’t delete arbitrary items cheaply.
“min and max, with deletions” Leftmost and rightmost nodes.
“iterate in key order” Inorder traversal visits keys sorted.

If you only need exact-key lookups, a hash map is faster (O(1) average). Reach for order only when the problem needs order.

How it works

Section titled “How it works”

Search and insert

Section titled “Search and insert”
  1. Start at the root. Compare the key with the node’s key.
  2. Equal: found (or, for insert, already present; a map would overwrite the value).
  3. Smaller: go left. Bigger: go right. If that child is empty, the key isn’t in the tree, and that empty spot is exactly where an insert hangs the new leaf.
bst_basic.py
from __future__ import annotations
from dataclasses import dataclass




@dataclass
class Node:
    key: int
    left: Node | None = None
    right: Node | None = None




def insert(root: Node | None, key: int) -> Node:
    if root is None:
        return Node(key)                      # 3. fell off the tree: the new key hangs here
    if key < root.key:                        # 1. compare, then go to the only side it can be on
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                               # 2. equal key: already present, keep it




def contains(root: Node | None, key: int) -> bool:
    n = root
    while n:                                  # one comparison per level: O(height)
        if key == n.key:
            return True
        n = n.left if key < n.key else n.right
    return False




def keys_in_order(n: Node | None) -> list[int]:
    return keys_in_order(n.left) + [n.key] + keys_in_order(n.right) if n else []




if __name__ == "__main__":
    root = None
    for k in [50, 30, 70, 20, 40, 60, 80, 35, 30]:
        root = insert(root, k)
    assert keys_in_order(root) == [20, 30, 35, 40, 50, 60, 70, 80]  # inorder = sorted
    assert contains(root, 35) and not contains(root, 45)
    assert not contains(None, 1)
    print("ok")

Delete (Hibbard deletion)

Section titled “Delete (Hibbard deletion)”

Delete is the only tricky operation, because removing an inner node leaves a hole that must be filled without breaking the order.

  1. Zero or one child: replace the node with its child (or with nothing). The child’s whole subtree was already on the correct side of the parent.
  2. Two children: find the successor, the leftmost node in the right subtree. It is bigger than everything on the left and smaller than everything else on the right, so it can stand in the hole.
  3. Copy the successor’s key into the node, then delete the successor from the right subtree. It has no left child (it’s the leftmost), so that’s always case 1.
bst_delete.py
from __future__ import annotations
from dataclasses import dataclass




@dataclass
class Node:
    key: int
    left: Node | None = None
    right: Node | None = None




def delete(root: Node | None, key: int) -> Node | None:
    """Hibbard deletion. Returns the new root of this subtree."""
    if root is None:
        return None                               # not found: nothing to do
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:                     # 1. zero or one child: splice it out
            return root.right
        if root.right is None:
            return root.left
        succ = root.right                         # 2. two children: successor is the
        while succ.left:                          #    leftmost node of the right subtree
            succ = succ.left
        root.key = succ.key                       # 3. copy it up, then delete it below
        root.right = delete(root.right, succ.key) #    (it has no left child: easy case)
    return root




def build(keys: list[int]) -> Node | None:
    def ins(n: Node | None, k: int) -> Node:
        if n is None:
            return Node(k)
        if k < n.key:
            n.left = ins(n.left, k)
        else:
            n.right = ins(n.right, k)
        return n
    root = None
    for k in keys:
        root = ins(root, k)
    return root




def inorder(n: Node | None) -> list[int]:
    return inorder(n.left) + [n.key] + inorder(n.right) if n else []




if __name__ == "__main__":
    root = build([50, 30, 70, 20, 40, 60, 80, 35])
    root = delete(root, 20)                       # leaf
    root = delete(root, 40)                       # one child (35)
    root = delete(root, 50)                       # two children: 60 takes the root
    assert root is not None and root.key == 60
    assert inorder(root) == [30, 35, 60, 70, 80]
    assert inorder(delete(root, 999)) == [30, 35, 60, 70, 80]
    print("ok")

What balanced trees give you

Section titled “What balanced trees give you”

A rotation is a local rewiring of three nodes that keeps inorder order but moves one node up and another down. Balanced trees do a few rotations on the way back up after an insert or delete.

Tree Rule it keeps Height bound Where you meet it
AVL subtree heights differ by ≤ 1 at every node < 1.44 · log₂ n read-heavy in-memory indexes
Red-black color rules: no red-red parent/child, equal black count on every path ≤ 2 · log₂(n + 1) .NET SortedDictionary / SortedSet, Java TreeMap, C++ std::map
Treap BST on keys + heap on random priorities O(log n) expected the easiest balanced tree to hand-roll (~40 lines)
Skip list not a tree: sorted linked lists with random express lanes O(log n) expected Redis sorted sets
B-tree / B+ tree many keys per node, all leaves at the same depth log_B n databases and file systems (disk pages)

Ordered maps per language

Section titled “Ordered maps per language”
Ordered map Ordered set Floor / ceiling / range
C# SortedDictionary<K,V> (red-black tree, O(log n) everything); SortedList<K,V> (two sorted arrays: O(log n) lookup, O(n) insert, index access) SortedSet<T> SortedSet.GetViewBetween(lo, hi) then .Min / .Max; SortedList.Keys + List.BinarySearch
Python none in the stdlib. Third-party sortedcontainers.SortedDict (often available, e.g. on LeetCode) sortedcontainers.SortedSet / SortedList bisect_left / bisect_right on a sorted list (see sorted containers)
TypeScript none. Map keeps insertion order, not key order none sorted array + your own binary search; hand-roll a treap if you need O(log n) inserts
Java / C++ (for reference) TreeMap / std::map TreeSet / std::set floorKey, ceilingKey, subMap / lower_bound, upper_bound
ordered_map.py
import bisect


# Python's stdlib has no balanced tree. Two honest options:
#   - `sortedcontainers.SortedDict` / `SortedList` (third-party, O(log n)-ish, often allowed)
#   - a dict for lookups + a sorted key list kept with bisect (O(n) insert, fine for modest n)




def neighbors(sorted_keys: list[int], x: int) -> tuple[int | None, int | None]:
    """(largest key < x, smallest key > x): the 'what's around x' query an ordered map gives you."""
    i = bisect.bisect_left(sorted_keys, x)     # first index with key >= x
    j = bisect.bisect_right(sorted_keys, x)    # first index with key > x
    below = sorted_keys[i - 1] if i > 0 else None
    above = sorted_keys[j] if j < len(sorted_keys) else None
    return below, above




if __name__ == "__main__":
    prices = {30: "c", 10: "a", 20: "b", 50: "e"}
    keys = sorted(prices)                      # [10, 20, 30, 50]
    bisect.insort(keys, 40)                    # O(log n) to find, O(n) to shift
    prices[40] = "d"
    assert keys == [10, 20, 30, 40, 50]
    assert neighbors(keys, 30) == (20, 40)
    assert neighbors(keys, 35) == (30, 40)
    assert neighbors(keys, 5) == (None, 10)
    assert [prices[k] for k in keys] == ["a", "b", "c", "d", "e"]  # iterate in key order
    print("ok")

What it costs

Section titled “What it costs”
Operation Plain BST, average (random order) Plain BST, worst Balanced BST Hash map Sorted array
search O(log n) O(n) O(log n) O(1) avg O(log n)
insert / delete O(log n) O(n) O(log n) O(1) avg O(n)
min / max O(log n) O(n) O(log n) (O(1) if cached) O(n) O(1)
floor / ceiling O(log n) O(n) O(log n) O(n) O(log n)
range of k keys O(log n + k) O(n) O(log n + k) O(n) O(log n + k)
in-order iteration O(n) O(n) O(n) needs a sort O(n)
memory 2 pointers + key per node + a color bit or height tightest

Every operation is “walk one path”, so everything is O(h). The only question is how big h gets. Slide n and compare:

Why balance matters: worst-case comparisons per search
drag the slider
Plain BST, sorted inserts
100
Plain BST, random inserts
14
Perfectly balanced (ideal)
7
Sorted input makes a plain BST a chain: n comparisons. Random order averages about 2.99 · log₂ n height in the worst path (and ~1.39 · log₂ n for a typical search), but one unlucky or adversarial order undoes it. A self-balancing tree stays within a small constant of the ideal ⌊log₂ n⌋ + 1 for every insertion order: AVL height is under 1.44 · log₂ n, red-black under 2 · log₂ n.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Ordered map vs ordered set. Same tree; the map stores a value next to each key.
  • Duplicates. Either store a count per node, or break ties by a secondary key (e.g. (score, id)) so all keys are unique.
  • Augmented trees. Store extra data per node and keep it updated through rotations: subtree size gives “k-th smallest” and “rank of x” in O(log n) (an order-statistic tree); subtree max-end gives an interval tree.
  • Iterators. Inorder successor without recursion: if there’s a right child, go right once then left all the way; otherwise climb until you come up from a left child.
  • Validation. “Is this a BST?” needs a valid (low, high) range passed down, not just comparing each node with its children.

Pitfalls

Section titled “Pitfalls”
  • Checking only parent vs child when validating. A node deep in the left subtree must be smaller than every ancestor it’s left of, not just its parent.
  • Assuming O(log n) for a plain BST. It’s only true on average. Sorted or nearly sorted input, which is common in real data, gives O(n).
  • Recursion depth on a degenerate tree. A 100,000-key chain overflows the stack in a recursive insert. Another reason to use a library tree.
  • Duplicate keys with no policy. Decide: reject, overwrite, count, or tie-break.
  • TS Map order. It’s insertion order. Sorting [...map.keys()] each query is O(n log n) per query.
  • .sort() without a comparator in JS sorts numbers as strings: [10, 9, 1].sort() is [1, 10, 9].
  • C# SortedList vs SortedDictionary. SortedList inserts are O(n) (array shifts). Fine for build-once, read-many; bad for heavy churn.

In the interview

Section titled “In the interview”
  • Ask: do I need order, or just lookup? If just lookup, say “a hash map is enough” and move on.
  • Name the guarantee you rely on: “An ordered map, so floor and ceiling are O(log n). In C# that’s SortedSet with GetViewBetween; in Python I’d use sortedcontainers if allowed, otherwise bisect on a list and accept O(n) inserts.”
  • Mention degeneration unprompted: “A hand-rolled BST is O(n) on sorted input, so I’d use a balanced one.”
  • Follow-ups to expect: “How would you find the k-th smallest quickly?” (augment with subtree sizes), “What if it doesn’t fit in memory?” (B-tree), “Why would a database prefer a B+ tree over a red-black tree?” (fewer, larger node reads from disk).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
You insert the keys 1, 2, 3, …, 1000 in that order into a plain (unbalanced) BST. How many comparisons does searching for 1000 take?
Check yourself
pick one
When deleting a node with two children, why does its inorder successor make a valid replacement?
Check yourself
pick one
You need: insert, delete, and 'smallest key ≥ x', each fast, with 10⁵ keys changing constantly. Which structure?

Practice on your own

Section titled “Practice on your own”

These are classic textbook exercises, not gym questions:

  • Validate that a binary tree is a BST (pass down the allowed range).
  • Build a height-balanced BST from a sorted array.
  • Find the inorder successor of a node, with and without parent pointers.
  • Trim a BST so it only contains keys in [lo, hi].
  • Hand-roll a treap with insert and search, and test it on sorted input.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Sorted containers and bisectThe practical ordered structures you'll actually use.
Binary treesTraversals: inorder is what makes BSTs sorted.
Heaps and priority queuesWhen you only ever need the minimum.
Binary searchThe same halving idea, on an array.