Binary Search Trees

Suppose you need a collection you can search quickly and modify constantly. A sorted array is great at searching — binary search finds anything in $O(\log n)$ — but inserting in the middle means shifting everything after it, which is $O(n)$. A linked list is the mirror image: inserting is $O(1)$ once you are there, but finding the spot means walking the whole list. A hash map is fast at both and gives up order entirely, so it cannot answer "what is the next price above 100.25?".

A binary search tree is the structure that refuses to choose. It keeps the data ordered like the sorted array, but its links let you insert and delete without moving anything else.

The invariant

Each node holds a key and has up to two children. The rule, applied at every node:

everything in the left subtree is smaller than this node's key; everything in the right subtree is larger.

That single invariant is the whole data structure. It means the comparison you make at a node tells you which subtree the answer must be in, exactly like the comparison in Binary Search Patterns tells you which half of an array to keep. Searching is: compare, go left or right, repeat. Inserting is: search for the key until you fall off the bottom, and put the new node there.

Every one of these operations walks a single root-to-leaf path, so the cost is not $O(\log n)$ — it is

$$O(h)$$

where $h$ is the height of the tree, the length of the longest root-to-leaf path. If the tree is balanced then $h \approx \log_2 n$ and everything is fast. If it is not, $h$ can be as large as $n$ and the tree degenerates into a linked list.

Worked example: build and search

Insert 8, 4, 12, 2, 6, 10, 13 into an empty tree. 8 becomes the root. 4 < 8 so it goes left; 12 > 8 so it goes right. 2 < 8, then 2 < 4, so it lands left of 4. 6 < 8 but 6 > 4, so right of 4. Similarly 10 and 13 sit under 12. You get the balanced tree above.

Now search for 13: compare with 8 (bigger, go right), compare with 12 (bigger, go right), compare with 13 — found. Three comparisons for seven nodes. Search for 7: 8 → left to 4 → right to 6 → right is empty, so 7 is not present, and you learned that in three steps too.

def search(node, key):        # O(h): h = log n balanced, n degenerate
    while node:
        if key == node.key:   return node
        node = node.left if key < node.key else node.right
    return None

def insert(node, key):        # same O(h) walk, then attach a leaf
    if node is None:          return Node(key)
    if key < node.key:  node.left  = insert(node.left,  key)
    elif key > node.key: node.right = insert(node.right, key)
    return node

Put beside the alternatives, the trade-off is clear:

Structure	Search	Insert / delete	Ordered walk, min, next-above?
Sorted array	$O(\log n)$	$O(n)$	yes
Linked list	$O(n)$	$O(1)$ at a known spot	yes, but slow to reach
Hash map	$O(1)$ average	$O(1)$ average	no
Balanced BST	$O(\log n)$	$O(\log n)$	yes

The BST is the only row that is fast in all three columns, and that last column is why order-sensitive systems keep reaching for it.

Worked example: deleting a node with two children

Delete 12 from the tree above. It has children 10 and 13, so you cannot just unhook it. The trick: replace its key with its in-order successor — the smallest key in its right subtree, which is 13 — then delete that successor from the right subtree, where it has at most one child and is easy to remove. The result keeps the invariant: everything left of the new 13 (namely 10) is still smaller, everything right is still larger. Deleting a node with zero or one child is simpler: splice the child (or nothing) into its place.

Where it shows up

In interviews: validate a BST, find the k-th smallest, lowest common ancestor, convert a sorted array to a balanced BST, and the in-order-successor question above. Expect the follow-up "what if the input arrives sorted?" — the answer is balancing.

In real systems the ordered map is a balanced BST. C++'s std::map and Java's TreeMap are red-black trees, and a limit Order Book Data Structure built on one gives you the best bid and offer in $O(\log n)$ plus an ordered walk of price levels for depth. Time-series indices, interval lookups ("which position was live at 09:31:04?") and risk-limit ladders use the same structure. When you need only the single best element and never the order below it, a heap is cheaper; when you need no order at all, use a hash map.