Binary search trees: the rule, traversal, deletion and TreeMap

← Back to the section

By now we have collected an awkward trade-off. A sorted array searches fast (binary search, O(log N)) but inserts slowly. A linked list inserts fast but searches slowly. And we would like both at once. A binary search tree gives exactly that: lookup, insertion and deletion all in O(log N) — as long as the tree stays balanced.

Terms

A tree is nodes connected by edges. The words you cannot avoid:

• root — the top node, the entry point into the tree;
• parent and child — the node above and the nodes attached below it;
• leaf — a node with no children, the edge of the tree;
• subtree — a node together with everything underneath it;
• level — the depth of a node: 0 at the root, 1 for its children, and so on.

"Binary" means every node has at most two children — a left one and a right one.

The search tree rule

A tree becomes a search tree thanks to a single rule: at any node, every key in the left subtree is smaller than the node's own key, and every key in the right subtree is larger. The rule holds at every node, not just at the root.

That is what makes lookup fast. To find a key we compare it with the root; smaller means go left, larger means go right, and we descend cutting off half of the tree at each step. It is the same binary search, only over a structure of nodes instead of an array.

Insertion and traversal

Insertion follows the same descent: we look for the place where the key is missing (an empty slot on the left or on the right at the bottom) and hang the new node there. That is O(log N) too in a balanced tree.

Traversal is a way of visiting every node. The most useful one is in-order: the left subtree first, then the node itself, then the right subtree. The magic is that an in-order traversal of a search tree hands back the keys in strictly ascending order — the tree is "sorted by itself".

Deletion is the trickiest operation

Deletion splits into three cases by the number of children the doomed node has:

1. no children (a leaf) — just unhook the node from its parent;
2. one child — "pull" the child up into the deleted node's place, as in a linked list;
3. two children — the hard case: the node cannot simply be yanked out. You find the successor — the smallest key in the right subtree, that is the next value up — and put it in the deleted node's place. The tree rule survives.

The degeneration problem

A search tree has an Achilles' heel. If keys are inserted in already sorted order (1, 2, 3, 4…), every new node clings to the right of the previous one, and the tree stretches into one long branch — effectively into a linked list. Lookup in it degrades to O(N).

live example

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

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

    static Node build(int... keys) {
        Node root = null;
        for (int key : keys) root = insert(root, key);
        return root;
    }

    static int depth(Node node) {
        return node == null ? 0 : 1 + Math.max(depth(node.left), depth(node.right));
    }

    static int steps(Node node, int key) {
        int count = 1;
        while (node.key != key) { node = key < node.key ? node.left : node.right; count++; }
        return count;
    }

    public static void main(String[] args) {
        Node mixed = build(50, 25, 75, 12, 37, 62, 88);
        Node sorted = build(12, 25, 37, 50, 62, 75, 88);
        System.out.println("mixed: depth " + depth(mixed) + ", steps to 88 - " + steps(mixed, 88));
        System.out.println("sorted: depth " + depth(sorted) + ", steps to 88 - " + steps(sorted, 88));
    }
}

The same seven keys: shuffled — depth 3 and three steps to the target; sorted — depth 7 and seven steps. On a million keys that is 20 steps against a million.

So the O(log N) promise holds only while the tree stays balanced — roughly the same depth in every direction. A plain search tree guarantees nothing of the sort. The fix is self-balancing trees that rebuild themselves on insert: red-black trees and 2-3-4 trees.

Trees beyond search: Huffman codes

Binary trees are useful for more than storage. The classic example is Huffman codes. The idea: give frequent symbols short bit codes and rare ones long codes (in an ordinary encoding every symbol takes the same room). The codes are built from a tree: symbols are the leaves, and the more frequent a symbol is, the closer to the root its leaf sits and the shorter the path to it. The tree is built bottom-up by repeatedly merging the two rarest symbols. Such a tree guarantees that no code is a prefix of another — which is why the compressed sequence can be decoded unambiguously.

How it is done in Java

The tree from this article is a teaching one: you do not need to write it in working code, the standard library already ships one, self-balancing out of the box, without the Achilles' heel. Understanding the machinery is still worth it — otherwise it is unclear what you are paying for when you take an ordered map.

The reference implementation is TreeMap (and TreeSet, which is just a TreeMap without values inside). Inside it is a red-black tree: on insert and delete it recolors and rotates nodes so that no branch stretches into a list. That is why sorted data, which kills the naive tree, is an ordinary case for TreeMap.

The complexity is honest, with no "on average" caveat: get, put, remove and containsKey are guaranteed O(log n) for any insertion order, with no worst case. That is exactly the difference from a hash table you are paying for: HashMap is faster (O(1) on average) but keeps no order at all.

Order is what you take TreeMap for: the keys always lie in ascending order, and operations appear that a hash table cannot have in principle:

• firstKey and lastKey — the smallest and the largest key in O(log n);
• floorKey, ceilingKey, higherKey, lowerKey — "the nearest key not greater than this one" and its neighbours — the very "next value up" we looked for as a successor when deleting;
• headMap, tailMap, subMap — range queries: every entry from one bound to another.

Importantly, subMap and its relatives return not a copy but a view of the same tree: writing into it changes the original map, and the other way round.

The main trap is this: TreeMap decides that two keys are equal by compareTo (or by the comparator), not by equals. For the tree two keys are the same when the comparison returned zero — and by no other measure.

live example

import java.util.Map;
import java.util.TreeMap;

public class TreeMapKeys {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
        map.put("Order", 1);
        map.put("order", 2);
        System.out.println("size: " + map.size());
        System.out.println("map: " + map);
    }
}

The two strings are not equal by equals, but the comparator considers them the same: there is one entry, its key is left over from the first insert and its value comes from the second. Objects whose compareTo looks at only some of their fields will glue together the same way. That is why the comparison used for TreeMap keys is made consistent with equals. And a small detail: under natural ordering TreeMap will not take null as a key — there is nothing to compare it against.

In short

• A binary search tree combines the fast lookup of a sorted array with the fast insertion of a list — everything in O(log N) while it is balanced.
• The rule: at every node the left subtree is smaller and the right one is larger. Lookup and insertion are a descent cutting off half at each step.
• An in-order traversal returns the keys in ascending order. Deleting a node with two children is solved by replacing it with its successor.
• A plain tree degenerates into a list when sorted data is inserted (O(N)); self-balancing trees are what guarantee the balance.
• Binary trees are used outside search too — for compression with Huffman codes, for instance.

What to read next

• Red-black trees — how rotations and recoloring stop a branch from stretching into a list.
• 2-3-4 trees and B-trees — a node with several keys, and why database indexes rest on it.
• Hash tables — access by key in O(1) when order is not needed.
• Heaps — a tree with a weaker rule that hands back the maximum instantly.