Binary Search Tree

A binary search tree (BST) is a binary tree where every node's left subtree contains smaller keys and right subtree contains larger keys. Average O(log n) operations on random input — but a plain BST is unbalanced and degrades to O(n) on sorted input.

Complexity

How it works

Search: start at the root; go left if the target is smaller, right if larger, until you find it or hit None. Insert: same descent, then attach the new node where None was. Delete: three cases — leaf (just remove), one child (splice), two children (replace with in-order successor and recurse).

Python implementation

class Node:
    __slots__ = ("key", "left", "right")
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None


class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):                      # avg O(log n), worst O(n)
        def _ins(node, key):
            if node is None:
                return Node(key)
            if key < node.key:
                node.left = _ins(node.left, key)
            elif key > node.key:
                node.right = _ins(node.right, key)
            return node
        self.root = _ins(self.root, key)

    def contains(self, key):                    # avg O(log n), worst O(n)
        node = self.root
        while node:
            if key == node.key: return True
            node = node.left if key < node.key else node.right
        return False

    def in_order(self):
        out = []
        def _walk(n):
            if n is None: return
            _walk(n.left); out.append(n.key); _walk(n.right)
        _walk(self.root)
        return out


bst = BST()
for k in [5, 3, 8, 1, 4, 7, 9]:
    bst.insert(k)
print(bst.in_order())     # [1, 3, 4, 5, 7, 8, 9]
print(bst.contains(7))    # True

Trade-offs

• Average O(log n); worst O(n) on sorted insertions — a plain BST is rarely the right choice.
• Supports ordered traversal and range queries (unlike a hash table).
• Use AVL, red-black, or B-trees for balanced guarantees.
• sortedcontainers.SortedList in Python gives you ordered set/dict semantics without the implementation cost.

← Back to Algorithms