# Binary Search Trees and Sorted Collections — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/t-bst

> Implement a BST and use bisect and sorted containers in practice.

## 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.

```python
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.

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

- [ ] O(1)
- [ ] O(log n)
- [ ] O(n log n)
- [x] O(n)

*Answer:* O(n). Sorted insertions create a chain-like tree with height n.