Binary Search Trees and Sorted Collections

Ordered data with fast search

A binary search tree (BST) keeps an ordering invariant: every key in a node's left subtree is smaller, and every key in the right subtree is larger. Search, insertion and deletion follow a single path, so they cost O(h), where h is the height: O(log n) when balanced, but O(n) when the tree degenerates, for example when keys are inserted in sorted order. Self-balancing trees (AVL, red-black, B-trees in databases) maintain O(log n) height through rotations. A BST also supports ordered queries that hash tables cannot: minimum and maximum, the next larger key (successor), range queries and iteration in sorted order. Python's standard library has no tree-based sorted map. In practice, use the bisect module to keep a sorted list (insort is O(n) because of shifting, but binary search is O(log n) and fast in C), or the third-party sortedcontainers package (SortedList, SortedDict), which is widely used and efficient. Implementing a BST yourself remains a great exercise and a common interview topic.

A BST and the bisect alternative

Insert, search and range queries; then the same with a sorted list.

from __future__ import annotations
import bisect
from dataclasses import dataclass
from typing import Iterator, Optional

@dataclass
class Node:
    key: int
    left: Optional[Node] = None
    right: Optional[Node] = None

class BST:
    def __init__(self):
        self.root: Optional[Node] = None

    def insert(self, key: int) -> None:
        if self.root is None:
            self.root = Node(key)
            return
        node = self.root
        while True:
            if key < node.key:
                if node.left is None:
                    node.left = Node(key); return
                node = node.left
            elif key > node.key:
                if node.right is None:
                    node.right = Node(key); return
                node = node.right
            else:
                return                                  # ignore duplicates

    def __contains__(self, key: int) -> bool:
        node = self.root
        while node and node.key != key:
            node = node.left if key < node.key else node.right
        return node is not None

    def range(self, lo: int, hi: int) -> Iterator[int]:   # keys in [lo, hi], in order
        def walk(node):
            if node is None:
                return
            if lo < node.key:
                yield from walk(node.left)
            if lo <= node.key <= hi:
                yield node.key
            if node.key < hi:
                yield from walk(node.right)
        yield from walk(self.root)

tree = BST()
for k in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(k)
print(40 in tree, 45 in tree)            # True False
print(list(tree.range(35, 65)))          # [40, 50, 60]

prices = []                              # practical alternative: a sorted list
for p in [50, 30, 70, 20, 40, 60, 80]:
    bisect.insort(prices, p)
lo, hi = bisect.bisect_left(prices, 35), bisect.bisect_right(prices, 65)
print(prices[lo:hi])                     # [40, 50, 60]

A guessing game

Searching a balanced BST is the number-guessing game where each answer ("higher" or "lower") halves the possibilities. A degenerate BST is a game where the host only ever says "higher", so you end up guessing every number.

Quick check: What is the worst-case search time in an unbalanced BST with n keys?

• O(1)
• O(log n)
• O(n log n)
• O(n)