Binary search tree explained: how it works, code and complexity

What problem a binary search tree solves

A sorted array gives fast binary search, but inserting a new element shifts everything after it. A hash table gives fast lookup and insert, but keeps no order, so it cannot answer "what is the smallest key larger than 42?" or "list all keys between 10 and 20". A binary search tree keeps keys sorted and still allows fast inserts and deletes. It is the basis of ordered maps and sets such as Java's TreeMap and C++'s std::map, which use self-balancing variants.

The rule in plain words

Each node has a key, an optional left child and an optional right child. For every node: all keys in its left subtree are smaller, and all keys in its right subtree are larger. To find a key, start at the root and compare: go left if the key is smaller, go right if it is larger, stop if it is equal or if you fall off the tree.

Worked example: building and searching a tree

Insert 8, 3, 10, 1, 6, 14, 4 in this order. Each new key walks down from the root and becomes a leaf where it falls off.

Searching for 4 compares with 8, 3, 6, then 4: four comparisons in a tree of seven keys. Searching for 7 compares with 8, 3, 6 and then finds no right child of 6, so 7 is not present.

Python implementation

Insert and search are short loops. Delete has three cases: the node has no children (remove it), one child (replace it with the child), or two children (copy in its in-order successor, the smallest key of the right subtree, then delete that successor).

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored
def contains(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None
def delete(root, key):
    if root is None:
        return None
    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:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root
def inorder(root):
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []

root = None
for k in [8, 3, 10, 1, 6, 14, 4]:
    root = insert(root, k)
print(inorder(root))                 # [1, 3, 4, 6, 8, 10, 14]
print(contains(root, 4), contains(root, 7))  # True False
root = delete(root, 3)               # node with two children
print(inorder(root), root.left.key)  # [1, 4, 6, 8, 10, 14] 4

Time and space complexity

The worst case is real, not theoretical: inserting already sorted keys (1, 2, 3, ...) into a plain BST gives every node only a right child, and the tree becomes a linked list. Random insertion orders give an expected height of O(log n).

Balanced variants and common mistakes

Self-balancing trees keep the height at O(log n) by restructuring with rotations after inserts and deletes.

• Validating a BST by checking only parent and child. Pass down a valid (low, high) range instead.
• Forgetting to return the (possibly new) root from recursive insert and delete, so changes are lost.
• Deep recursion on a degenerate tree: Python's default recursion limit is about 1000, so a chain of 5000 nodes crashes recursive code. Use loops or keep the tree balanced.
• Undefined duplicate policy: decide whether duplicates are ignored, counted, or always go to one side.

When to use a BST and typical interview questions

Use a balanced BST when you need ordered data with frequent inserts and deletes: range queries, floor and ceiling lookups, rank statistics, or iterating in sorted order. Use a hash table when you only need exact-key lookup. In Python, the standard library has no tree map; common choices are a sorted list with the bisect module for small or mostly static data, or the third-party sortedcontainers package.

Typical interview questions: validate a BST, find the k-th smallest element (in-order traversal), lowest common ancestor, convert a sorted array to a balanced BST (pick the middle as the root), and find the in-order successor of a node.