Tries

A tree where paths spell words

In a trie, no node stores a whole word. Instead, each link from parent to child represents one character, and a word is the path you walk from the root. Store cat and car, and the two words share the path c then a, splitting only at the final letter. The root represents the empty string; every node represents some prefix of the stored words.

One question remains: how do you know where words end? After inserting cat, the path c-a-t exists, but so does the path c-a. Is ca a stored word or just a prefix on the way to something? Each node carries a boolean flag, often called isWord, marking spots where a complete word ends. Without it, a trie could not tell its words from its prefixes.

A node in Java is a small class: an array of 26 child references (one slot per lowercase letter, where slot 0 means 'a' and slot 25 means 'z') plus the flag. The child for character c lives at index c - 'a'. A null slot means no stored word continues with that letter from here.

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord = false;
}

Insert and search: walk the letters

Both core operations are simple walks from the root, one character at a time. To insert a word, look at each character in turn and follow the matching child link, creating the node first if the slot is null. When the last character's node is reached, set its isWord flag. Inserting cat into an empty trie creates three nodes; inserting car afterward creates only one, because c and a already exist. That sharing is where tries save space across large dictionaries of similar words.

To search for a word, do the same walk without creating anything. If a needed child is null anywhere along the way, the word is not stored. If you complete the walk, the word exists only if the final node's isWord flag is true. Reaching c-a while only cat was inserted must report false.

void insert(TrieNode root, String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        int i = c - 'a';
        if (node.children[i] == null) {
            node.children[i] = new TrieNode();
        }
        node = node.children[i];
    }
    node.isWord = true;
}

Prefix search: the trie's superpower

Checking whether any stored word starts with a given prefix is the same walk yet again, with one relaxation: when the walk completes, do not check isWord. Merely surviving the walk proves at least one word continues below, because trie nodes only exist as part of some inserted word.

This is what a hash set fundamentally cannot do. A HashSet answers is this exact word present in O(1), but it scatters words by hash, so words sharing a prefix land nowhere near each other. Answering does anything start with app means testing every entry. The trie physically groups words by prefix: everything starting with app lives below one node, three steps from the root. Autocomplete becomes walk to the prefix node, then collect the words in the subtree beneath it.

boolean startsWith(TrieNode root, String prefix) {
    TrieNode node = root;
    for (char c : prefix.toCharArray()) {
        int i = c - 'a';
        if (node.children[i] == null) return false;
        node = node.children[i];
    }
    return true;
}

Why it is O(word length), and what it costs

Look back at the loops: insert, search, and startsWith each perform one array access per character of the input. If the word has L characters, that is O(L), and n, the number of stored words, appears nowhere. A prefix lookup against a million-word trie costs exactly as many steps as against a ten-word trie. Compare that with checking a sorted list, where binary search alone costs O(log n) string comparisons.

The price is memory. Every node carries 26 references, most of them null in a typical English dictionary, so tries trade space for that flat lookup time. When the alphabet is large or memory is tight, implementations swap the array for a HashMap<Character, TrieNode> per node. Slightly slower, much leaner. Recognize the trie trigger words in problems: prefix, autocomplete, dictionary, and starts with.

Tries and heaps and BSTs are all trees. Structures with one root and no cycles. Next we drop those restrictions entirely and let nodes connect however they like. That is a graph, and it can model almost anything.

Frequently asked