What is a binary search tree (BST) and what are its operation complexities?

Question

Accepted Answer

A **binary search tree** is a binary tree with an ordering invariant: for every node, **all keys in its left subtree are smaller**, and **all keys in its right subtree are larger**. This lets you search by halving the problem at each step.

## The invariant

```text
        8
       / \
      3    10
     / \     \
    1   6     14     left < node < right at every node
```

## Search and insert

```python
def search(node, key):
    while node:
        if key == node.val: return node
        node = node.left if key < node.val else node.right  # go one way
    return None

def insert(node, key):
    if node is None: return Node(key)
    if key < node.val: node.left  = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node
```

## Complexity

| Operation | Balanced | Worst (degenerate) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

The **worst case** occurs when keys are inserted in sorted order — the tree degenerates into a linked list of height `n`.

## Trade-offs

- **Strengths:** ordered traversal in O(n); supports range queries and successor/predecessor.
- **Weaknesses:** no balance guarantee on its own — needs an AVL or red-black variant to stay O(log n).

## Why it matters

BSTs give you sorted, dynamic data with logarithmic operations — the conceptual ancestor of database indexes and ordered maps.

The degeneration problem motivates **self-balancing trees**, a key follow-up topic in interviews.