You load yesterday’s order IDs from a CSV. They come out sorted. You insert them into a binary search tree because “search is O(log n).” After a million rows, every lookup walks a million nodes. You built a linked list and paid tree-shaped rent for the privilege. The ordering law is honest. The height is not a promise.

A binary search tree keeps every left descendant smaller than the node and every right descendant larger. Search, insert, and delete walk one path from the root. That path is O(height), not “O(log n)” unless the tree stays bushy. Already-sorted input is how it becomes a spine.

This post is the representation: the invariant, the three core operations, why an inorder walk is sorted, and why Java does not ship java.util.BST. Height, Big-O, and worst-case vs amortized live on the Data Structures Roadmap. We will not re-lecture them here.

The invariant is the whole structure

A binary tree is nodes with at most two children. A BST adds a law about where keys sit:

for every node:
  all keys in the left subtree  <  node.key
  all keys in the right subtree >  node.key

That law is recursive. It is not enough that the left child is smaller; every key under that child must be smaller. Violate it once and search will walk the wrong branch and miss a key that is sitting in the tree.

A node is two pointers and a key. A value field can ride along; it does not change the walk:

final class Node {
    int key;
    Node left;
    Node right;

    Node(int key) {
        this.key = key;
    }
}

Note: Duplicates need a policy: reject, overwrite a value, count occurrences, or park equals on one side. Pick one and keep the invariant true. The snippets below treat equals as “already present” (set semantics).

Search follows one comparison per level

Start at the root. Equal — found. Smaller — go left. Larger — go right. Null — not there. No other branch is legal, because the invariant says the missing key cannot hide on the side you skipped.

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

Each step throws away one subtree. If the tree is bushy, you throw away about half the remaining keys — that is the log n people quote. If the tree is a stick, you throw away one node. Same code. Different height. Different bill.

The minimum is the leftmost node; the maximum is the rightmost. Both are the same walk with the other child:

Node min(Node node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

Insert is search until the hole

Insert does not pick a clever slot. It searches until it falls off a null child, then hangs a new node there. Recursion makes the reattachment obvious: the caller stores the returned child.

Node insert(Node node, int key) {
    if (node == null) {
        return new Node(key);
    }
    if (key < node.key) {
        node.left = insert(node.left, key);
    } else if (key > node.key) {
        node.right = insert(node.right, key);
    }
    return node;
}

A balanced-looking tree is an accident of insert order, not a feature of this code. There is no rotation, no height field, no “fixup.” That is why this layout is cheap to explain and unsafe to trust under sorted input.

Inorder is sorted — that is the point

Inorder is left subtree, then the node, then the right subtree. The invariant makes that sequence sorted: everything on the left is smaller, everything on the right is larger, and the node sits in the gap.

void inorder(Node node, List<Integer> out) {
    if (node == null) {
        return;
    }
    inorder(node.left, out);
    out.add(node.key);
    inorder(node.right, out);
}

Walk this tree:

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

Left of 8 is 1, 3, 4, 6, 7. Then 8. Then 10, 14. The full visit is 1, 3, 4, 6, 7, 8, 10, 14. You did not sort. You read the layout. That is the job a hash table cannot do: hashing answers “is this key here?” without promising an order.

Delete: three shapes, one successor

Delete is search, then a patch that restores the invariant. Three shapes, not twenty interview variants.

No children. The node is a leaf. Replace it with null.

One child. Replace the node with that child. The child’s subtree already obeys the invariant relative to the parent.

Two children. You cannot promote both children. Copy the inorder successor (the minimum of the right subtree — the next larger key) into the node, then delete that successor from the right subtree. The successor has no left child, so that second delete is a 0- or 1-child case.

Node delete(Node node, int key) {
    if (node == null) {
        return null;
    }
    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;
        }
        if (node.right == null) {
            return node.left;
        }
        Node successor = min(node.right);
        node.key = successor.key;
        node.right = delete(node.right, successor.key);
    }
    return node;
}

Predecessor (max of the left) works symmetrically. Either keeps the invariant. Cost is still O(height).

Do not “delete” by leaving a tombstone flag unless you have a compaction plan. Height does not shrink; search still pays for the node.

Sorted input is a linked list with extra pointers

Insert 1, 2, 3, 4 into the insert above:

1
 \
  2
   \
    3
     \
      4

Every new key is larger than the root, so every insert walks the whole right spine and hangs off the end. Height is n. contains(4) does four comparisons. contains(1_000_000) after a million sequential IDs does a million. You still have two child pointers per node. Only one of them is ever used.

The same keys in a mixed order stay short:

Insert 2, 4, 1, 3:

    2
   / \
  1   4
     /
    3

Height 3, not 4. Search still follows the same contains loop. The loop did not get smarter. The shape did.

Production data loves this failure: timestamps, auto-increment IDs, a CSV that was already sorted, a log replayed in order. An unbalanced BST quotes O(log n) and delivers O(n) on the input you are most likely to feed it. From the roadmap: worst-case is the bill you pay on the next call, not a rarity you can amortize away.

Java has no java.util.BST

There is no teaching BST in the JDK. TreeMap and TreeSet are red-black trees: they keep the BST invariant and rebalance so height stays Θ(log n) even if you insert sorted keys. This post will not teach rotations or color flips. The name is enough: if you needed a BST in production Java, you already had one, and it is not the class above.

NavigableMap<Integer, String> orders = new TreeMap<>();
orders.put(42, "paid");
orders.put(7, "pending");
orders.put(19, "packed");
// iteration is 7, 19, 42 — sorted keys, guaranteed log n per mutate

Reach for TreeMap when you need ordered keys (range views, firstKey / lastKey, successor). Reach for HashMap when you need a key and do not care about order. Rolling your own Node is for learning the walk, for an interview whiteboard, or for a layout the JDK does not ship. It is not the default sorted map.

Note: TreeMap is still a tree of objects, not a contiguous array. It wins on order-plus-log-n, not on cache scans. If the job is “I will sort once and binary-search a list,” a sorted ArrayList can be the cheaper layout. Match the hot operation, as the roadmap asks.

When not to use a (plain) BST

Skip an unbalanced BST when:

  • You need a guaranteed log n under sorted or adversarial keys — use a balanced tree (TreeMap / TreeSet in the JDK; AVL or red-black if you are implementing). The unbalanced BST’s average case assumes random-ish insert order. Production keys are often not random-ish.
  • You do not need order. Lookup-only uniqueness is a hash table’s job. A tree’s extra pointers and comparisons are a tax you are not spending.
  • n is tiny. A list and a linear scan will beat a tree of twenty objects. Measure before you celebrate log n.
  • The data lives on disk. Databases use wide, page-sized nodes (B-trees), not binary nodes, because a disk round-trip is the expensive operation. A BST of records is the wrong shape for that bill.

Use a BST (usually TreeMap) when the hot path needs ordered keys and log-height updates: a sorted leaderboard you mutate, a range of timestamps, “next key after this one.” If the sentence does not mention order, you probably wanted a hash table.

How to read the bill

Same shopping-list reading as the roadmap: pick the structure for the operation on the hot path.

Structure: binary search tree (unbalanced)
search     O(h)     — h = height; log n if bushy, n if a spine
insert     O(h)
delete     O(h)
inorder    O(n)     — visits every node; yields sorted keys
min / max  O(h)     — walk left / right
space      O(n)     — two child pointers per key

h is the variable that people erase when they write O(log n) on the slide. For this layout, write O(h) until a balancer is in the picture.

Cheat sheet

Invariant:  left subtree < node < right subtree
Walk:       compare, go left or right; cost is height
Insert:     search to null, hang the node
Delete:     leaf / one child / two children via inorder successor
Inorder:    left, node, right — that sequence is sorted
Degenerate: sorted (or reverse-sorted) inserts → a linked list
JDK:        no java.util.BST; TreeMap / TreeSet are red-black
Skip:       need guaranteed log n (balance); no order (hash)

Do:

  • Name order as a requirement before you name a tree.
  • Treat search cost as O(height) on an unbalanced BST.
  • Use TreeMap / TreeSet when production Java needs sorted keys.

Don’t:

  • Quote O(log n) on a BST you never rebalance.
  • Insert already-sorted IDs or timestamps into a teaching BST and call it an index.
  • Use a tree when a hash table would do and you never iterate in key order.

Wrap-up

A BST is an ordered binary tree, not a balanced one. The invariant makes search a single path and makes inorder a sort you do not have to run. Insert and delete are that same path plus a local patch. Feed it sorted keys and the path is the whole set: O(n) with two unused-looking child pointers per node.

In Java, the production type with this job is TreeMap (red-black), not a hand-rolled Node. If you do not need order, you did not need a tree. If you need order and a height guarantee, you needed a balancer — which is a later layout, not a slogan you stamp on this one.

For the glossary behind height, worst-case, and “what operation is hot,” stay on the Data Structures Roadmap.

Next optional step in the series Next-best in O(log n) without a full sort. Heaps: Priority Without Sorting All