Binary Search Trees: One Rule for Fast Search, Insert, and Delete

Someone says, “I’m thinking of a number between 1 and 100 — guess it, and I’ll only ever tell you higher or lower.” You don’t start at 1 and count up. You say 50. “Higher.” 75. “Lower.” 62. “Higher.” In about seven guesses you’ve cornered any number out of a hundred, because every single guess throws away half of what’s left.

That move — kill half the possibilities with one comparison — is the entire idea behind the binary search tree (BST): one of the most-asked data structures in interviews, and the quiet engine behind ordered maps, database indexes, and every “what’s the next-biggest one?” query you’ve ever run. By the end of this article, you and I will have built one together — search, insert, the in-order walk that hands you your data pre-sorted, and the delete that trips up most candidates.

Let's start nowhere near a computer

Forget the one-off guessing game and picture something you can keep. You’re a receptionist, and guests arrive one by one, each holding a numbered ticket. You want any later guest to be found in seconds, so instead of a pile you build a tree of signposts.

The first guest becomes the top signpost. Every signpost holds a number and obeys one unbreakable rule:

Looking for something smaller than me? Step left. Bigger? Step right.

When a new guest arrives, they walk down from the top, obeying each signpost — smaller, go left; bigger, go right — until they reach an empty spot, and they plant their own signpost there. To find a ticket later, you replay the exact same walk. Searching and inserting are the same journey; one plants a signpost at the end, the other just checks what’s there.

Two things fall out of that single rule, and they’re the heart of everything below:

1. Every step halves the crowd. Reading a signpost tells you which entire half the ticket is in — the other half stops existing for you, exactly like “higher / lower.”
2. The whole tree is secretly sorted. From any signpost, everything to its left is smaller and everything to its right is bigger. Walk the tree left-to-right and the numbers come out in order, without you ever running a sort.

That’s a binary search tree. Everything else is turning the signpost rule into code — including the genuinely fiddly question of what to do when a signpost in the middle of the tree has to leave.

The same trick, all over your day

Once you know the shape, you meet it constantly. The ordered map in your standard library (TreeMap / TreeSet) is a BST under the hood, which is why it can answer “give me every key between 100 and 200” or “what’s the smallest key ≥ 150?” — questions a hash map simply can’t. A leaderboard that shows you the next rank up, a scheduler that grabs the next event by time, autocomplete-by-range — all the same descend-by-comparison walk.

But the most illuminating cousin lives in your database. Every index you’ve ever created is a search tree over your rows, and WHERE created_at BETWEEN ? AND ? is a tree walk to the low end followed by an in-order sweep to the high end. Databases don’t use a plain BST, though, and the reason is the punchline of this whole article. They use a B-tree: same left-smaller / right-bigger ordering, but each node holds hundreds of keys and has hundreds of children, and the tree is kept rigidly balanced at all times. Why fan out so wide? Because reading a node means a disk seek, and a fat, shallow tree of height 3 or 4 touches the disk three or four times instead of thirty. Same skeleton — ordered keys, descend by comparison — but reshaped around the one weakness we’re about to find in the plain version. Hold that thought.

What a binary search tree actually looks like

Let’s store seven numbers — 50, 30, 70, 20, 40, 60, 80 — as a BST. Here’s the shape, and it’s worth staring at:

The rule that makes this a search tree is called the BST invariant, and here it is in one line:

For every node, all keys in its left subtree are smaller, and all keys in its right subtree are bigger.

Read “every node,” not “every node versus its two children.” The invariant is about the whole subtree, not the immediate kids — the 40 hanging under 30 isn’t just bigger than 30, it’s smaller than 50, the grandparent it lives beneath. That subtlety is exactly what a 50 → 30 → 40 path encodes, and mixing it up is the classic bug we’ll return to in the interview corner.

Let's build one, step by step

We’ll build it in small pieces and assemble the whole class at the end.

Step 1: the node

A signpost holds a number and points to two smaller signposts — left and right. That’s the entire node.

private static final class Node {
    int key;
    Node left;
    Node right;
 
    Node(int key) {
        this.key = key;
    }
}

The tree itself is just a reference to the top signpost, the root. An empty tree is root == null.

Step 2: search — replay the guessing game

Searching is the receptionist’s walk. Start at the root. Equal? Found it. Smaller? Go left. Bigger? Go right. Fall off the bottom (null) and the key was never here.

Look at what the walk didn’t do: it never glanced at 70, 60, 80, or 20. The instant 40 < 50 was true, the entire right half of the tree stopped mattering. Three comparisons for seven keys — and it’d still be a handful of comparisons for seven million.

public boolean search(int key) {
    Node node = root;
    while (node != null) {
        if (key == node.key) {
            return true;
        }
        node = key < node.key ? node.left : node.right;
    }
    return false;
}

No recursion needed — a search is a single straight path from root to a leaf, so a while loop that keeps reassigning node walks it in O(h), where h is the height of the tree. (That h is doing quiet, load-bearing work. Come back to it.)

Step 3: insert — walk, then plant

Insertion is that same search, with one twist: instead of giving up when you fall off the bottom, you plant a new signpost right where you fell off.

Inserting 65 walks 50 → 70 → 60, then tries to step right from 60, finds nothing there, and hangs 65 as 60’s new right child. It slotted into the one and only place the invariant allows — because the walk is the invariant, comparison by comparison.

public void insert(int key) {
    root = insert(root, key);
}
 
private Node insert(Node node, int key) {
    if (node == null) {
        return new Node(key);          // fell off the edge — plant here
    }
    if (key < node.key) {
        node.left = insert(node.left, key);
    } else if (key > node.key) {
        node.right = insert(node.right, key);
    }
    return node;                       // key == node.key → already here, ignore
}

This is the recursive shape you’ll reuse for delete, so it’s worth reading closely. Each call returns “the subtree that should now hang here.” Usually that’s the same node you were handed (return node), but at the empty spot it’s a brand-new node, and the parent quietly re-hooks it with node.left = insert(...). That “rebuild the link on the way back up” pattern is the trick that makes deletion clean too.

Step 4: in-order — the free sort

Here’s the payoff for keeping everything ordered. Visit a node’s left subtree, then the node, then its right subtree — recursively — and the keys come out perfectly sorted. No comparisons, no swaps; the sorting already happened, one insert at a time.

public List<Integer> inorder() {
    List<Integer> out = new ArrayList<>();
    inorder(root, out);
    return out;
}
 
private void inorder(Node node, List<Integer> out) {
    if (node == null) {
        return;
    }
    inorder(node.left, out);          // everything smaller, in order
    out.add(node.key);                // then me
    inorder(node.right, out);         // then everything bigger, in order
}

That “left, me, right” order is the invariant read aloud. Swap two lines and you get pre-order or post-order — the same three pieces in a different sequence — but only this order tracks the ranges from small to large. It’s also your best debugging friend: after any operation, an in-order walk that isn’t sorted means you’ve broken the invariant somewhere.

Step 5: delete — the case everyone fumbles

Now the hard one. Deleting from a BST is where most candidates wobble, because a node in the middle of the tree is holding two whole subtrees together, and you can’t just yank it out.

Watch the tempting bug first. Say you delete 50 (the root) by doing the obvious thing — cut its link, set it to null:

// found 50 ... just remove it?
node = null;   // wrong: 30, 70, and everything under them just fell off the tree

You didn’t delete one key; you dropped half the tree on the floor. The whole subtlety of BST deletion is: how do you remove a node without orphaning what it was holding up? The answer splits into three cases, and the first two are easy.

Case 1 — a leaf. No children, nothing hanging below. Just unhook it. Deleting 20 above costs one null.

Case 2 — one child. The node is a link in a chain. Splice it out: hand its single child (and everything under it) straight up to its parent. Deleting 30 when its only child is 45 means 45 slides into 30’s slot — every key underneath is still on the correct side of every ancestor, because the whole block just moved up one level.

Case 3 — two children. This is the real puzzle. You can’t promote both children into one slot. So you don’t move a subtree at all — you find a replacement value that can legally sit where the deleted key was, copy it in, and then delete that value from where it used to live.

Which value can stand in for 50? It has to be bigger than everything in the left subtree and smaller than everything in the right subtree — otherwise the invariant snaps. Exactly two values qualify: the largest key on the left (the in-order predecessor) or the smallest key on the right (the in-order successor). Let’s use the successor: the smallest key in the right subtree, which you find by stepping right once and then left, left, left until you can’t.

For our tree the successor of 50 is 60. Copy 60 up into the root, and now the tree reads correctly again — 60 really is bigger than 30, 20, 40 and smaller than 70, 80. But there are momentarily two 60s, so we delete the original 60 from the right subtree. And here’s the quiet gift: the successor is the leftmost node of the right subtree, so it has no left child — deleting it is always Case 1 or Case 2, never Case 3. The hard case defuses itself into an easy one.

public void delete(int key) {
    root = delete(root, key);
}
 
private Node delete(Node node, int key) {
    if (node == null) {
        return null;                   // key isn't here — nothing to remove
    }
    if (key < node.key) {
        node.left = delete(node.left, key);
    } else if (key > node.key) {
        node.right = delete(node.right, key);
    } else {
        // found it — the three cases
        if (node.left == null) {
            return node.right;         // leaf (both null) or right child only
        }
        if (node.right == null) {
            return node.left;          // left child only
        }
        // two children: overwrite with the in-order successor,
        // then delete that successor from the right subtree
        Node successor = min(node.right);
        node.key = successor.key;
        node.right = delete(node.right, successor.key);
    }
    return node;
}
 
private Node min(Node node) {
    while (node.left != null) {         // smallest key = keep turning left
        node = node.left;
    }
    return node;
}

The first two returns handle all of Cases 1 and 2 at once: if there’s no left child, whatever’s on the right (a subtree, or null for a leaf) is exactly what should hang here. The else block is Case 3, and its last line is a recursive delete that we know bottoms out in an easy case. Notice the pattern from insert again: every path returns the subtree that should now sit at this spot, and the parent re-hooks it with node.left = delete(...). That’s what quietly repairs every link on the way back up.

How fast is this, really?

Every operation we wrote — search, insert, delete — is a single walk from the root down one path. So they all cost O(h), the height of the tree. The entire performance story is one question: how tall does the tree get?

When keys arrive in a nicely mixed order, the tree stays bushy and h ≈ log₂ n. Seven keys, height 3; a million keys, height ~20. That’s the dream.

But the tree’s shape is a fossil of the insertion order, and there’s a worst case that bites in real life. Insert keys that are already sorted — 10, 20, 30, 40, 50 — and every one is bigger than the last, so every one goes right. You don’t get a tree. You get a straight line:

Now h = n, and your O(log n) search has quietly become O(n) — a linked list wearing a tree costume. And sorted (or reverse-sorted) input isn’t exotic: it’s exactly what you get from a timestamped log, an auto-increment ID column, or a “helpfully” pre-sorted file. A plain BST does not self-balance, and this is its one fatal flaw.

Here’s where it lands against the two structures you’d otherwise reach for:

Read the last two rows — that’s the BST’s reason to exist. A hash map crushes it on raw point lookups but is utterly blind to order: ask a hash map for the next-biggest key or everything in a range and it has no choice but to scan and sort. A sorted array matches the tree on search and beats it on min, but every insert or delete shoves half the array over. The BST is the structure that keeps ordered queries and cheap edits at the same time — as long as you can keep it balanced.

That “as long as you can keep it balanced” is why production code almost never ships a raw BST. Self-balancing trees — red-black trees (what TreeMap actually is), AVL trees, and the disk-friendly B-trees from earlier — do a little rotation work on every insert and delete to guarantee h = O(log n), killing the skew forever. They’re the plain BST plus a balance discipline, and understanding the plain one is the entire prerequisite.

The complete implementation

Everything above, assembled into one class you can whiteboard from memory:

package dev.fiveyear.bst;
 
import java.util.ArrayList;
import java.util.List;
 
public final class BinarySearchTree {
 
    private static final class Node {
        int key;
        Node left;
        Node right;
 
        Node(int key) {
            this.key = key;
        }
    }
 
    private Node root;
 
    /** Adds a key, ignoring duplicates. O(h). */
    public void insert(int key) {
        root = insert(root, key);
    }
 
    private Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key); // fell off the edge — plant the new node here
        }
        if (key < node.key) {
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            node.right = insert(node.right, key);
        }
        return node; // key == node.key → already present, do nothing
    }
 
    /** True if the key is stored. O(h). */
    public boolean search(int key) {
        Node node = root;
        while (node != null) {
            if (key == node.key) {
                return true;
            }
            node = key < node.key ? node.left : node.right;
        }
        return false;
    }
 
    /** Removes a key if present, keeping the invariant intact. O(h). */
    public void delete(int key) {
        root = delete(root, key);
    }
 
    private Node delete(Node node, int key) {
        if (node == null) {
            return null; // key was never here — nothing to remove
        }
        if (key < node.key) {
            node.left = delete(node.left, key);
        } else if (key > node.key) {
            node.right = delete(node.right, key);
        } else {
            if (node.left == null) {
                return node.right; // leaf (both null) or right child only
            }
            if (node.right == null) {
                return node.left; // left child only
            }
            // two children: overwrite with the in-order successor, then
            // delete that successor from the right subtree
            Node successor = min(node.right);
            node.key = successor.key;
            node.right = delete(node.right, successor.key);
        }
        return node;
    }
 
    // The smallest key in a subtree: keep turning left until you can't.
    private Node min(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
 
    /** Every key in ascending order (left, node, right). */
    public List<Integer> inorder() {
        List<Integer> out = new ArrayList<>();
        inorder(root, out);
        return out;
    }
 
    private void inorder(Node node, List<Integer> out) {
        if (node == null) {
            return;
        }
        inorder(node.left, out);
        out.add(node.key);
        inorder(node.right, out);
    }
}

And here it is doing everything we drew, with the exact outputs it produces:

BinarySearchTree bst = new BinarySearchTree();
for (int k : new int[] {50, 30, 70, 20, 40, 60, 80}) {
    bst.insert(k);
}
 
bst.inorder();   // [20, 30, 40, 50, 60, 70, 80]  — sorted, for free
bst.search(40);  // true
bst.search(45);  // false — the walk fell off the bottom
 
bst.delete(20);  // Case 1: a leaf, just unhooked
bst.delete(30);  // Case 2: one child (40 slides up)
bst.delete(50);  // Case 3: two children (successor 60 takes its place)
bst.inorder();   // [40, 60, 70, 80]  — still sorted, invariant intact

The interview corner

BSTs show up constantly — as the structure itself, and hidden inside “validate this tree,” “find the k-th smallest,” or “what’s the lowest common ancestor.” Here’s how to not fumble the round.

Ask these before you write a line:

• “Do keys have to be unique, or do I handle duplicates?” It changes the equality branch — ignore, keep a count, or always send equals one fixed direction. Say which and why.
• “Can I assume the tree stays balanced, or do I need guaranteed O(log n)?” This is the tell that separates candidates. If they need guarantees, you’re reaching for a balanced tree, and naming that unprompted is a strong signal.
• “What’s the traffic — read-heavy, write-heavy, ordered scans?” It decides whether a plain BST, a balanced tree, or even a hash map is the honest answer.

The follow-up ladder — each rung a new scenario, with a one-line answer:

1. “Validate that a tree is a BST.” Don’t compare each node to its children only — that passes broken trees. Recurse carrying a (low, high) range and check every node fits its window. It’s the range idea from the tip, made into code.
2. “Find the k-th smallest key.” An in-order walk emits keys in sorted order, so stop at the k-th. Augment each node with its subtree size and you get O(h) instead of O(k).
3. “The tree keeps degenerating on sorted input — fix it.” Self-balance: red-black or AVL rotations keep height O(log n) no matter the insert order. TreeMap is a red-black tree for exactly this reason.
4. “It’s billions of rows on disk, not in RAM.” Switch to a B-tree / B+ tree: high fan-out so the tree is shallow and each node is one disk page — the same ordering, reshaped for seeks. This is every database index.
5. “Many threads read and write it at once.” A single lock kills throughput; reach for lock-free/optimistic balanced trees or a concurrent skip list (ConcurrentSkipListMap), which gives ordered-map semantics with far friendlier concurrency.

Three mistakes that fail the round:

• Deleting a two-child node by moving a subtree instead of copying the in-order successor’s value — you either orphan a subtree or break the invariant.
• Validating with only parent-vs-child comparisons. The invariant is about entire subtrees / ranges; a node can beat its parent yet still violate an ancestor.
• Claiming O(log n) and stopping there. Height is O(log n) only if the tree is balanced. Say “O(h), which is O(log n) balanced and O(n) in the worst case” and you’ve shown you actually understand it.

Where to go from here

You now own the core: left is smaller, right is bigger, and every operation is one walk down that rule. Three natural next stops, each one a way to fix or extend the height problem:

• Self-balancing trees — AVL (strictly balanced, read-optimised) and red-black (looser, fewer rotations, the default in standard libraries). Learn the four rotations once and both click.
• B-trees / B+ trees — the plain BST reshaped for disk: wide, shallow, always balanced. This is the data structure behind essentially every SQL index.
• Treaps and skip lists — two clever ways to get expected O(log n) from randomness instead of rotations, which makes them delightfully short to implement.

And if you enjoyed the descend-by-comparison shape, the trie plays the same game over the letters of a word, while Dijkstra’s algorithm leans on the same “grab the smallest next” move a balanced tree makes cheap. Next time your database returns a range query in a millisecond, you’ll know it’s just a receptionist walking a very well-organised tree of signposts.