Tries

A trie — a prefix tree — stores strings by their characters, one node per character, words spelled out along the paths from the root. The name comes from retrieval and is usually pronounced "try", to distinguish it from "tree".

The shape

insert: car, cargo, care, do, dog

        (root)
        /    \
       c      d
       |      |
       a      o*
       |      |
       r*     g*
      / \
     g   e*
     |
     o*

* marks the end of a word

Two things to read off that. Shared prefixes are stored once — "car", "cargo" and "care" share three nodes. And the asterisks are load-bearing: do is a word and a prefix of dog, so a node needs to say whether a word ends there.

The node

    private static final class Node {
        // A HashMap, not a 26-slot array. The array version is faster and is what interview
        // answers usually show, but it silently assumes lowercase ASCII - it breaks on digits,
        // apostrophes and every non-English alphabet.
        final Map<Character, Node> children = new HashMap<>();
        boolean endOfWord;
    }

The usual textbook version uses Node[] children = new Node[26], which is faster and smaller per node — and which quietly assumes your alphabet is lowercase English. It breaks on digits, on an apostrophe in "don't", and on every language that is not English. That is a substantial assumption to bury in an array size:

        // Non-alphabetic characters - the case a 26-slot array cannot represent.
        Trie mixed = new Trie();
        mixed.insert("a1");
        mixed.insert("don't");
        Check.isTrue(mixed.contains("a1"), "digits work");
        Check.isTrue(mixed.contains("don't"), "punctuation works");

Insert and look up

    /** O(m) in the length of the word. */
    public void insert(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new Node());
        }
        if (!node.endOfWord) {
            node.endOfWord = true;
            size++;
        }
    }

Walk the characters, creating nodes as needed, and flag the last one. computeIfAbsent collapses the get-check-put into one call.

⚠️ contains is not startsWith

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

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

Both walk the same path. Only contains checks endOfWord. Without that flag a trie holding only "cargo" would report that it contains "car", "carg" and "ca" — every prefix becomes a false member. It is the standard trie bug, and the tests pin the distinction:

        Check.isTrue(!trie.contains("ca"), "a prefix that was never inserted is not a word");
        Check.isTrue(trie.startsWith("ca"), "but it IS a prefix");

⚠️ Do not use a trie for exact lookup

The claim you will read is that a trie gives O(m) lookup in the length of the word, independent of how many words it holds — implying it beats a HashSet.

It does not. Hashing a string also reads every character, so HashSet.contains is O(m) too. And the HashSet does it with one pass over contiguous memory and one array index, where the trie does m separate HashMap lookups and m pointer dereferences to scattered nodes.

For "does this word exist", a HashSet is simpler and faster. Choosing a trie there is the classic case of picking the clever structure over the right one.

What a trie is actually for

Prefix questions — the ones a hash set cannot answer at all without scanning everything.

    /** Autocomplete: every word under a prefix. This is what a trie is actually for. */
    public List<String> wordsWithPrefix(String prefix) {
        List<String> out = new ArrayList<>();
        Node start = find(prefix);
        if (start != null) {
            collect(start, new StringBuilder(prefix), out);
        }
        out.sort(String::compareTo);   // deterministic, since HashMap iteration order is not
        return out;
    }

Walk to the prefix node, then collect every word beneath it. The cost is O(m + number of matches) — you never look at a word that does not match. A HashSet would have to test every element it holds.

    private void collect(Node node, StringBuilder path, List<String> out) {
        if (node.endOfWord) {
            out.add(path.toString());
        }
        for (Map.Entry<Character, Node> e : node.children.entrySet()) {
            path.append(e.getKey());
            collect(e.getValue(), path, out);
            path.deleteCharAt(path.length() - 1);   // backtrack, or the paths concatenate
        }
    }

That deleteCharAt is the backtracking step and the easiest line to omit. One StringBuilder is shared across the whole traversal, so after descending into a child you must undo the character before trying the next sibling. Leave it out and the paths concatenate into nonsense.

        Check.eq(trie.wordsWithPrefix("car").toString(), "[car, care, cargo]", "autocomplete");
        Check.eq(trie.wordsWithPrefix("do").toString(), "[do, dog]", "prefix that is also a word");
        Check.eq(trie.wordsWithPrefix("").toString(), "[car, care, cargo, do, dog]", "empty prefix is everything");

Trie against HashSet

Where they are used

• Autocomplete and typeahead — the canonical case.
• Spell checkers — walk the trie allowing a bounded number of edits.
• IP routing — longest-prefix matching on address bits.
• Word games — Boggle and Scrabble solvers prune a search the moment the current path stops being a prefix of any word, which is the trie doing real work.

A radix tree (or Patricia trie) compresses chains of single-child nodes into one node holding a whole substring, which cuts the memory cost substantially on sparse data. It is the same idea with the obvious inefficiency removed.

What to remember

• One node per character; shared prefixes are stored once.
• endOfWord is what separates a word from a prefix — omit it and every prefix matches.
• For exact lookup, use a HashSet. A trie is not faster there.
• Use one for prefix queries, which a set cannot answer.
• Backtrack the path buffer when collecting, or the results concatenate.
• A Map of children handles alphabets a 26-slot array cannot.