The search box fires on every keystroke. Your handler filters eighty thousand product names with startsWith. It works in staging. It hitch-steps in production once the catalog is real. Nobody wrote a “bad loop.” They stored strings in a shape that cannot answer prefix cheaply.

A trie stores strings by shared prefixes. Each character is an edge. Autocomplete and dictionary lookup become a walk down those edges — not a scan of every word. Terms this series will not re-teach (ADT vs implementation, how to read a complexity table) live on the Data Structures Roadmap.

The scan autocomplete should not do

A list (or a HashSet) holds whole strings. Asking “which of these start with ca?” means looking at each key:

List<String> hits = catalog.stream()
        .filter(name -> name.startsWith(prefix))
        .limit(10)
        .toList();

That is one comparison per stored word, and each comparison may read up to prefix.length() characters. The catalog size n is on the hot path. Type three more letters and you pay it again.

A hash table does not help here. HashSet.contains("cat") is cheap for an exact key. It has nothing to say about “everything that starts with ca.” TreeMap can fake a prefix with a range of keys; that is ordered search, not shared prefixes. The layout that makes prefix cheap is a tree of characters.

A node is children plus an end mark

A trie node is small. It does not store the word. It stores how to continue, and whether a word ends here.

PieceJob
ChildrenNext character → child node. A Map<Character, Node> for a general alphabet, or an array of size 26 when you only store a–z.
End marktrue if some inserted word stops at this node.

The end mark is not optional. Without it, ca is indistinguishable from a prefix of cat. Insert both and you need both facts: a walk can stop (ca is a word) and continue (cat is a word).

Three words sharing a stem look like this (* is the end mark):

root
 ├─ c → a ┬─ t*          cat
 │        └─ r* → t*     car, cart
 └─ d → o → g*           dog

cat, car, and cart share the path c → a. dog shares only the root. That sharing is the whole point: one node per distinct prefix, not one entry per string.

When the alphabet is a–z only, children collapse to an array. Index is c - 'a'; a null slot means “no edge”:

private static final class Node {
    final Node[] children = new Node[26];
    boolean endOfWord;
}

Note: The array form is faster and more compact when the alphabet is tiny and dense. The map form is the honest default for Unicode, mixed case, or punctuation. A 65,536-slot array per node is how a “simple” trie turns into a memory problem — more on that below.

Insert, search, and prefix

Insert walks one character at a time. Missing children are created. The last node gets the end mark.

public final class Trie {
    private static final class Node {
        final Map<Character, Node> children = new HashMap<>();
        boolean endOfWord;
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            node = node.children.computeIfAbsent(c, k -> new Node());
        }
        node.endOfWord = true;
    }
}

Insert cat, then car. The second word reuses c → a and only allocates r:

insert("cat")  create c, a, t    mark t
insert("car")  reuse  c, a       create r, mark r
contains("ca") false             walked to a; end mark is off
hasPrefix("ca") true             the node exists

Same class. Search is that walk plus a question the walk itself cannot answer: did a word end here?

    public boolean contains(String word) {
        Node node = walk(word);
        return node != null && node.endOfWord;
    }

    public boolean hasPrefix(String prefix) {
        return walk(prefix) != null;
    }

    private Node walk(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            node = node.children.get(s.charAt(i));
            if (node == null) {
                return null;
            }
        }
        return node;
    }

contains("ca") is false after you insert only cat. hasPrefix("ca") is true. That is the end mark doing its job.

Autocomplete is “walk the prefix, then collect every end mark in the subtree.” The walk is O(length of prefix). The collect is O(size of the matching subtree), not O(n) over the whole catalog:

    public List<String> suggestions(String prefix, int limit) {
        Node node = walk(prefix);
        if (node == null || limit <= 0) {
            return List.of();
        }
        List<String> out = new ArrayList<>();
        collect(node, new StringBuilder(prefix), out, limit);
        return out;
    }

    private void collect(Node node, StringBuilder path, List<String> out, int limit) {
        if (out.size() >= limit) {
            return;
        }
        if (node.endOfWord) {
            out.add(path.toString());
        }
        for (var e : node.children.entrySet()) {
            path.append(e.getKey());
            collect(e.getValue(), path, out, limit);
            path.deleteCharAt(path.length() - 1);
        }
    }

There is no java.util.Trie. The JDK gives you HashMap / HashSet for exact keys and TreeMap for sorted keys. Prefix-shaped data is a layout you build (or take from a library) when that is the hot operation.

What the bill looks like

Read this as a shopping list, the way the roadmap taught: pick the structure whose expensive operations are ones you rarely perform.

Structure: trie
insert(word)       O(L)     L = length of the word
contains(word)     O(L)     walk + end mark
hasPrefix(p)       O(P)     P = length of the prefix
suggestions(p)     O(P + k) k = size of the matching subtree
space              O(nodes) one node per distinct prefix

Cost tracks key length, not how many keys you stored. That is the opposite of the startsWith scan, where n sits on every keystroke. Space is the trade: you pay a node for every distinct prefix. A dictionary of English words shares a lot. A set of random UUIDs shares almost nothing — the trie degrades into a skinny tree that is larger than a HashSet of the same keys.

When not to use a trie

Skip a trie when:

  • The set is small or you only need exact lookup — fifty feature flags, a session-token set, a dictionary of a few hundred codes. HashSet.contains is the layout. A trie is extra nodes for a job hashing already finishes.
  • The alphabet is huge and you do not compress — per-node maps of arbitrary Unicode, or a fat array indexed by code point, blow memory before they blow time. Compressed / radix / PATRICIA tries exist for this; an uncompressed node-per-character trie is the wrong default for URLs, full Unicode, or binary keys.
  • You need suffix or substring search — a trie answers prefixes of stored keys. “Does cat appear inside any stored string?” is a different job. That is a suffix array, a suffix tree, or an Aho–Corasick automaton — not this structure with the end mark flipped.

A TreeMap<String, V> is also the wrong substitute when the pain is prefix sharing. It keeps keys ordered so a range can approximate “starts with ca.” It does not share the characters, and lookup still pays tree height in keys, not a walk of L characters. Reach for it when you need sorted iteration or range queries, not autocomplete.

Cheat sheet

Node:     children (map or small array) + endOfWord
insert:   walk, create missing edges, mark the last node
contains: walk, then endOfWord must be true
prefix:   walk only — the node existing is enough
suggest:  walk the prefix, collect end marks in the subtree
cost:     O(length), independent of n
JDK:      no Trie; HashSet = exact, TreeMap = sorted

Do:

  • Use a trie when the hot operation is prefix: autocomplete, dictionary lookup, IP / URL routing, T9-style typing.
  • Prefer a Map of children unless the alphabet is tiny and dense.
  • Treat the end mark as data. A path can be both a word and a prefix of a longer word.

Don’t:

  • Filter a list with startsWith on every keystroke and call it search.
  • Build a trie for a handful of keys a HashSet would hold.
  • Expect suffix or “contains this infix” queries from a prefix tree.
  • Allocate a huge child array “to be general.” Compression exists; a 64K slot per node is not it.

Wrap-up

A trie is a layout for strings whose hot question is “what continues from here?” Insert, exact search, and prefix check are walks of the key. Autocomplete is that walk plus a bounded collect. The catalog size drops off the hot path; key length and the matching subtree remain.

Use it when many keys share stems and prefix is the operation you run constantly. Use a HashSet when you only ask “is this exact string present?” Use a different string index when the query is a suffix or a substring. The glossary, the skill path, and the rest of the series live on the Data Structures Roadmap.

Next optional step in the series Adjacency list vs matrix before any algorithm. Graphs: Pick the Layout First