Trie — The Data Structures Atlas

Category: Trees

The problem

A Hash Table answers "is this exact key present?" in O(1) average, but it can't answer "is there any key starting with this prefix?" without scanning every stored key — hashing throws away any structural relationship between similar keys on purpose. Autocomplete, prefix validation, and "does continuing to type this make sense" all need that relationship preserved.

The solution

Store keys character by character down a tree: each node holds its children keyed by the next character, and one flag per node marks "a complete key ends here." Looking up a key or a prefix means walking one character at a time from the root — cost is O(m) where m is the length of the key or prefix, and critically, that cost has nothing to do with how many other keys are stored. A trie holding 100 keys and one holding 100,000 answer the same prefix query in the same time, because the walk only ever touches nodes along one path.

flowchart TD
    R((root)) --> P((p))
    P --> PI((i))
    PI --> PIX(("x*"))
    PIX --> PIX1((1))
    PIX --> PIX2((2))

* marks a node where a complete key ends (e.g. "pix" itself is a registered key, and so are "pix1" and "pix2").

Operation	Cost	Why
`insert(key)`	O(m)	one node created or reused per character of `key`
`contains(key)`	O(m)	walks the exact path for `key`, checks the end-of-word flag
`startsWith(prefix)`	O(m)	walks the exact path for `prefix`, existence alone is enough

m = key/prefix length. None of these depend on how many other keys are stored — see the benchmark below.

Classic example

classic/Trie builds each node's children as a Map<Character, Node> rather than a fixed 26/128-slot array, since PIX keys aren't restricted to one alphabet (letters, digits, @, ., +). TrieTest covers a real bug caught while writing it: the root node exists unconditionally as a field (not created by insert), so startsWith("") on a completely empty trie would otherwise return true — an empty-trie guard in startsWith fixes it, and the test locks the correct (false) behavior in.

Applied example: BACEN PIX-key prefix index

applied/PixKeyPrefixIndex validates and autocompletes PIX keys (BACEN-registered keys can be a CPF, email, phone number, or random UUID-style key) as a user types one into a payment form, without a directory-service round trip on every keystroke: hasKeyStartingWith backs the autocomplete UI, isRegisteredKey is the exact-match check once typing is done. PixKeyPrefixIndexTest covers both.

Benchmark

./gradlew :trees:trie:jmh

Real run (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork). Key length is held constant (12-character keys, "PIX" + a 9-digit zero-padded number) while the number of stored keys varies — the deliberately different shape from every other module's benchmark, since the claim here is that this axis shouldn't matter at all:

Operation	100 keys	10,000 keys	100,000 keys
`contains`	102.0 ns	98.7 ns	98.2 ns
`startsWith`	73.5 ns	89.2 ns	58.4 ns

Flat within noise across a 1,000x increase in stored key count — neither operation cares how many other keys share the trie. Contrast with Hash Table, where an exact-match lookup is also flat by size but can't answer a prefix query at all without an O(n) scan of every key.

When not to use it

Keys aren't naturally hierarchical/character-sequenced, or prefix queries are never needed? A Hash Table gives the same O(1)-ish exact-match lookup with much lower memory overhead per key (a trie allocates a node per unique character position, which adds up for a large, low-prefix-overlap key set).
Need range queries (all keys between X and Y), not prefix queries? A Binary Search Tree is the better fit for that shape of question.
Very long keys with little shared prefix structure make the per-character node overhead cost more than it saves — a trie earns its keep on data with real prefix locality (words, PIX keys, file paths, URLs), not arbitrary long strings.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :trees:trie:jacocoTestReport

Report at trees/trie/build/reports/jacoco/test/html/index.html.

Unit tests

src/test/java/com/datastructures/trees/trie/classic/TrieTest.java

package com.datastructures.trees.trie.classic;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;

class TrieTest {

    @Test
    void startsEmpty() {
        Trie trie = new Trie();

        assertThat(trie.isEmpty()).isTrue();
        assertThat(trie.size()).isZero();
    }

    @Test
    void insertThenContainsFindsTheExactKey() {
        Trie trie = new Trie();

        trie.insert("cat");

        assertThat(trie.contains("cat")).isTrue();
        assertThat(trie.size()).isEqualTo(1);
        assertThat(trie.isEmpty()).isFalse();
    }

    @Test
    void containsIsFalseWhenTheKeyWasNeverInserted() {
        Trie trie = new Trie();
        trie.insert("cat");

        assertThat(trie.contains("dog")).isFalse();
    }

    @Test
    void containsIsFalseForAStoredPrefixThatWasNeverInsertedAsItsOwnKey() {
        Trie trie = new Trie();
        trie.insert("caterpillar");

        // "cat" exists as a path through the trie (it's a prefix of "caterpillar"), but it was
        // never itself inserted as a complete key, so contains() must say no.
        assertThat(trie.contains("cat")).isFalse();
        assertThat(trie.startsWith("cat")).isTrue();
    }

    @Test
    void insertingTheSameKeyTwiceDoesNotDoubleCountSize() {
        Trie trie = new Trie();
        trie.insert("cat");

        trie.insert("cat");

        assertThat(trie.size()).isEqualTo(1);
        assertThat(trie.contains("cat")).isTrue();
    }

    @Test
    void insertingKeysThatShareAPrefixReusesTheSharedNodes() {
        Trie trie = new Trie();
        trie.insert("car");

        trie.insert("card"); // shares "car" with the first key, then extends with "d"

        assertThat(trie.contains("car")).isTrue();
        assertThat(trie.contains("card")).isTrue();
        assertThat(trie.size()).isEqualTo(2);
    }

    @Test
    void startsWithIsTrueForAnyStoredPrefixOfAKey() {
        Trie trie = new Trie();
        trie.insert("caterpillar");

        assertThat(trie.startsWith("c")).isTrue();
        assertThat(trie.startsWith("cate")).isTrue();
        assertThat(trie.startsWith("caterpillar")).isTrue();
    }

    @Test
    void startsWithIsFalseWhenNoStoredKeyMatchesThePrefixAtAll() {
        Trie trie = new Trie();
        trie.insert("cat");

        assertThat(trie.startsWith("dog")).isFalse();
    }

    @Test
    void startsWithIsFalseWhenThePrefixDivergesPartwayThroughAStoredKey() {
        Trie trie = new Trie();
        trie.insert("cat");

        // Shares "ca" with the stored key but diverges at the third character.
        assertThat(trie.startsWith("cow")).isFalse();
    }

    @Test
    void emptyStringIsAPrefixOfEverythingAndTheEmptyKeyIsHandledAsAWordItself() {
        Trie trie = new Trie();

        assertThat(trie.startsWith("")).isFalse(); // nothing stored yet at all

        trie.insert("");

        assertThat(trie.contains("")).isTrue();
        assertThat(trie.startsWith("")).isTrue();
        assertThat(trie.size()).isEqualTo(1);

        trie.insert("cat");

        assertThat(trie.startsWith("")).isTrue();
        assertThat(trie.size()).isEqualTo(2);
    }
}

src/test/java/com/datastructures/trees/trie/applied/PixKeyPrefixIndexTest.java

package com.datastructures.trees.trie.applied;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;

class PixKeyPrefixIndexTest {

    private final PixKeyPrefixIndex index = new PixKeyPrefixIndex();

    @BeforeEach
    void registerAFewPixKeysOfDifferentTypes() {
        index.register("12345678900"); // CPF-style key
        index.register("leon.gomes@example.com"); // email key
        index.register("+5511999998888"); // phone key
        index.register("a1b2c3d4-e5f6-7890-abcd-ef1234567890"); // random UUID-style key
    }

    @Test
    void anExactlyRegisteredKeyIsRecognizedAsRegistered() {
        assertThat(index.isRegisteredKey("leon.gomes@example.com")).isTrue();
    }

    @Test
    void aKeyThatWasNeverRegisteredIsNotRecognized() {
        assertThat(index.isRegisteredKey("someone-else@example.com")).isFalse();
    }

    @Test
    void autocompleteRecognizesAPartiallyTypedPrefixOfARegisteredKey() {
        assertThat(index.hasKeyStartingWith("leon.")).isTrue();
        assertThat(index.hasKeyStartingWith("+5511")).isTrue();
    }

    @Test
    void autocompleteRejectsAPrefixThatMatchesNoRegisteredKey() {
        assertThat(index.hasKeyStartingWith("99999")).isFalse();
    }

    @Test
    void anEmptyIndexHasNoStartingMatchesAndNoRegisteredKeys() {
        PixKeyPrefixIndex emptyIndex = new PixKeyPrefixIndex();

        assertThat(emptyIndex.hasKeyStartingWith("1")).isFalse();
        assertThat(emptyIndex.isRegisteredKey("12345678900")).isFalse();
    }
}

View full JaCoCo coverage report →