Binary Search Trees

The problem

You are building a contacts app. Every time someone types a name, you need the matching record — fast. A plain array of contacts works until you hit a few hundred thousand entries, then each lookup scans the whole list and the search box starts to lag on every keystroke.

You could keep the array sorted and binary-search it. That makes lookups quick, but the moment someone adds a new contact you have to shift thousands of elements to keep the order. Reads are fast and writes are slow. You want both to be cheap.

A first attempt

The obvious fix is a sorted array plus binary search. Lookups become O(log n) — lovely.

But inserting into a sorted array means finding the spot (O(log n)) and then sliding every later element over by one to make room (O(n)). Deletion has the same problem. So a workload that mixes reads and writes still costs O(n) per update. The sorted array optimized the wrong half of the job.

The array is rigid: its order lives in positions, so changing the order means moving data. What if the order lived in links instead, so inserting was just re-pointing?

The insight

Take the binary-search idea — "compare, then discard half" — and freeze it into structure. Store each value in a node with two children. Put everything smaller than a node in its left subtree and everything larger in its right subtree. That single invariant is the whole idea:

For every node: all keys in the left subtree < node's key < all keys in the right subtree.

Now a search is a binary search that walks pointers. At each node you compare once and step left or right, throwing away an entire subtree. And inserting is cheap: walk to where the key belongs and hang a new leaf there — no shifting. This is a Binary Search Tree (BST).

How it works

Here is the tree you get by inserting 8, 3, 10, 1, 6, 14, 4, 7:

          8
        /   \
       3      10
      / \       \
     1   6       14
        / \
       4   7

Searching for 7: 7 < 8 go left, 7 > 3 go right, 7 > 6 go right, found. Three comparisons instead of scanning eight values.

The code

A BST is just nodes plus the compare-and-branch rule. Here is the node type and a search.

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

def search(root, target):
    node = root
    while node is not None:
        if target == node.key:
            return node
        node = node.left if target < node.key else node.right
    return None  # not found

class BSTNode {
  key: number;
  left: BSTNode | null = null;
  right: BSTNode | null = null;
  constructor(key: number) {
    this.key = key;
  }
}

function search(root: BSTNode | null, target: number): BSTNode | null {
  let node = root;
  while (node !== null) {
    if (target === node.key) return node;
    node = target < node.key ? node.left : node.right;
  }
  return null; // not found
}

class Node {
    int key;
    Node left, right;
    Node(int key) { this.key = key; }
}

Node search(Node root, int target) {
    Node node = root;
    while (node != null) {
        if (target == node.key) return node;
        node = target < node.key ? node.left : node.right;
    }
    return null; // not found
}

#include <stdlib.h>

struct Node {
    int key;
    struct Node *left, *right;
};

struct Node *search(struct Node *root, int target) {
    struct Node *node = root;
    while (node != NULL) {
        if (target == node->key) return node;
        node = target < node->key ? node->left : node->right;
    }
    return NULL; /* not found */
}

struct Node {
    int key;
    Node *left = nullptr, *right = nullptr;
    Node(int k) : key(k) {}
};

Node *search(Node *root, int target) {
    Node *node = root;
    while (node != nullptr) {
        if (target == node->key) return node;
        node = target < node->key ? node->left : node->right;
    }
    return nullptr; // not found
}

Complexity

The log n only holds while the tree stays roughly balanced. Insert already-sorted keys and each new value goes to the far right — the tree degrades into a linked list of height n.

When to use it

Practice

Recap

• A BST stores keys so that left < node < right at every node, turning binary search into a pointer walk.
• Search, insert, and delete are all O(log n) when the tree is balanced, and O(n) when insertion order makes it degenerate into a list.
• Its superpower over a hash table is order: sorted iteration, min/max, and range queries come almost for free.