Binary Search Trees

A tree where left descendants are smaller and right descendants are larger. Ordered data with O(log n) operations — when balanced.

Level: intermediate

What is it?

A binary search tree (BST) stores keys in nodes, each with a left and a right child. For every node, all keys in its left subtree are smaller and all in its right subtree are larger. Search, insert, and delete follow one path from the root, so they cost O(height). An in-order traversal visits keys in sorted order. Self-balancing variants (AVL, red-black) keep the height at O(log n).

Why does it matter?

A BST keeps data sorted while allowing fast inserts and lookups, which arrays (slow inserts) and hash tables (no order) cannot both do. Ordered maps and sets in standard libraries are balanced trees, and databases use the multiway cousin, the B-tree.

Mental model

A game of 20 questions where each answer sends you left or right. At every node you compare and discard a whole side of the tree. If you always answer 'bigger', though, the tree degenerates into one long chain — a linked list.

How it works

Invariant: left subtree < node < right subtree, at every node.
Search, insert, and delete are O(h), where h is the height.
Balanced: h ≈ log₂ n. Degenerate (inserting sorted keys): h = n and everything is O(n).
In-order traversal (left, node, right) yields sorted order.
Deleting a node with two children means replacing it with its in-order successor or predecessor.
Self-balancing trees (AVL, red-black) rotate to keep the height logarithmic; B-trees widen nodes to match disk pages.

Steps

Start at the root
Compare the key with the node
Go left if smaller, right if larger
Insert where the path ends
In-order visit gives sorted keys

Code example: Insert and in-order traversal

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

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]:
    root = insert(root, k)
print(inorder(root))   # [1, 3, 6, 8, 10]

Complexity and trade-offs

Time: Search/insert/delete O(log n) balanced, O(n) worst case

Space: O(n)

Trade-offs

Keeps keys ordered: range queries, min, max, predecessor, and successor are cheap
An unbalanced tree degrades to a list; balancing adds implementation complexity
More pointer chasing than an array, so slower in practice for small data

Real-world usage

Ordered maps and sets (TreeMap, std::map)
Database indexes (B-trees and B+ trees are the disk-friendly version)
Schedulers and interval structures using balanced trees

Common mistakes

Assuming a plain BST is always O(log n).
Forgetting to handle duplicate keys deliberately.
Implementing delete with two children incorrectly.

Interview questions

What is the worst case of a BST and how do you avoid it?

Inserting keys in sorted order makes a chain of height n, so operations are O(n). Use a self-balancing tree (AVL, red-black) or randomize insertion order.

How do you validate that a tree is a BST?

Recursively pass down the allowed range: each node's key must be between the lower and upper bounds inherited from its ancestors, not just larger than its left child and smaller than its right child. Alternatively check that in-order output is strictly increasing.

Why do databases use B-trees rather than binary trees?

A B-tree node holds many keys and matches a disk page, so one read narrows the search by a large factor and the tree is very shallow. A binary tree would need many more page reads.