Tries

The trie (prefix tree) coding pattern for interviews. Insert, search and startsWith in O(length), wildcard search and Word Search II with a trie and DFS, with a step-through, code in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Mid-level13 min read

Read first: Tree traversal

A hash set answers “is this word stored?” in O(1). It can’t answer “does any stored word start with ca?” without checking every word. A trie, also called a prefix tree, answers both. It is a tree where each edge is one letter. The path from the root to a node spells a prefix. Words that start the same way share the same path, so a prefix query is just a walk down the tree.

A lookup costs O(L) for a word of length L. It doesn’t depend on how many words are stored, a thousand or a million. That’s why tries sit behind autocomplete, spell checkers and routing tables. In interviews they appear in two forms. You build one from scratch, or you use one to guide a DFS, so a search can stop the moment no word can match.

How to spot it

“Prefix”, “starts with”, “autocomplete” or “suggestions”.
Many words searched at once, as in Word Search II. One trie of all the words replaces one search per word.
A wildcard such as . that matches any letter. The trie lets you try each child.
“Shortest root” or “longest word built one letter at a time”. Both are walks that stop at word ends.
The largest XOR of two numbers. A trie of bits, from the top bit down, picks the opposite bit at each level.

For one lookup of whole words only, a hash set is simpler and just as fast. Reach for a trie when prefixes matter, or when many searches share work.

Watch it run

Insert car, cat, cart and dog, then search. Watch the shared nodes: cat reuses c and a, and cart reuses all of car. Then watch why search("ca") is false while startsWith("ca") is true.

words amber node: a word ends there

empty

def insert(word):
node = root
for letter in word:
node = add_child(node, letter)
node.is_word = True
def find(prefix): # search, startsWith
node = root
for letter in prefix:
if no child letter: return None
node = node.children[letter]
return node # search: is_word too

A trie starts as one empty root. Each node will stand for one prefix, spelled by the path down to it.

1 / 9

The difference between those two calls is one flag. Both walk to the same node. startsWith only needs the node to exist. search also needs a word to end there. That’s why car and cart can both be stored. The node for r has a child, and it’s also a word end.

The template

A trie with insert, search and startsWith, plus a search where . matches any letter:

Trie.javatrie.pyTrie.cstrie.gotrie.ts

public class Tries {
    public static void main(String[] args) {
        Trie trie = new Trie();
        for (String word : new String[] {"car", "cat", "cart", "dog"}) trie.insert(word);
        check(trie.search("cat") && trie.search("car") && trie.search("cart"));
        check(!trie.search("ca")); // a prefix, not a word
        check(trie.startsWith("ca") && !trie.startsWith("cow"));
        check(trie.searchWithDots("c.t") && trie.searchWithDots("..."));
        check(!trie.searchWithDots("d."));
        check(!new Trie().search("") && new Trie().startsWith(""));
        System.out.println("ok: Trie insert, search, startsWith and searchWithDots");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

// One node per prefix. The path from the root spells the prefix, and isWord marks where a whole
// word ends, since a word can also be the prefix of a longer one ("car" in "cart").
class TrieNode {
    TrieNode[] children = new TrieNode[26]; // lowercase a to z: index by letter - 'a'
    boolean isWord;
}

class Trie {
    private final TrieNode root = new TrieNode();

    void insert(String word) {
        // Walk down one letter at a time, adding nodes that don't exist yet. Words that share a
        // prefix share its nodes. O(L) for a word of length L.
        TrieNode node = root;
        for (char letter : word.toCharArray()) {
            int slot = letter - 'a';
            if (node.children[slot] == null) node.children[slot] = new TrieNode();
            node = node.children[slot];
        }
        node.isWord = true;
    }

    private TrieNode walk(String prefix) {
        // Follow the letters from the root. Missing a child means no stored word has this
        // prefix. O(L), however many words are stored.
        TrieNode node = root;
        for (char letter : prefix.toCharArray()) {
            node = node.children[letter - 'a'];
            if (node == null) return null;
        }
        return node;
    }

    boolean search(String word) {
        TrieNode node = walk(word);
        return node != null && node.isWord; // the path exists and a word ends here
    }

    boolean startsWith(String prefix) {
        return walk(prefix) != null; // any path at all means some word continues it
    }

    boolean searchWithDots(String word) {
        // Search where "." matches any letter. A dot can't pick one child, so it tries them all:
        // that's a DFS over the trie. O(L) without dots, up to O(26^dots · L) with them.
        return matchesFrom(root, word, 0);
    }

    private boolean matchesFrom(TrieNode node, String word, int position) {
        if (position == word.length()) return node.isWord;
        char letter = word.charAt(position);
        if (letter == '.') {
            for (TrieNode child : node.children) {
                if (child != null && matchesFrom(child, word, position + 1)) return true;
            }
            return false;
        }
        TrieNode nextNode = node.children[letter - 'a'];
        return nextNode != null && matchesFrom(nextNode, word, position + 1);
    }
}

Look at search_with_dots. For a normal letter it follows one child, as before. For a dot it tries every child, and returns true if any of them matches the rest. That’s a DFS over the trie, in the same shape as backtracking. It’s still fast in practice, because a branch dies as soon as the trie has no child for the next letter.

Variations

Word Search II

Find which of many words appear in a letter grid. Searching the grid once per word repeats the same work again and again. Instead, put all the words in a trie. Start a DFS from each cell, and move down the trie as you move across the grid. When the next cell’s letter has no child, stop that path. When you reach a node with a word, add it to the answer. Then clear its is_word, so it’s found only once. Removing leaf nodes once they’re used makes later searches faster still.

Autocomplete

Search Suggestions System returns up to three words for each prefix the user types. Walk one node down per typed letter. The suggestions are the first three words in the subtree under that node. With an array of 26 children, a DFS visits them in sorted order. Store the top three at each node during insert, and each keystroke becomes O(1).

Values at nodes

A node can hold more than a flag. Map Sum Pairs stores at each node the sum of the values of all words below it. A count of words below a node tells how many words share that prefix. Update these numbers on the way down during insert.

A trie of bits

To find the largest XOR of two numbers in a list, insert each number as 32 bits, top bit first. For each number, walk down and prefer the child with the opposite bit, since a 1 in a high bit is worth more than all the lower bits together. That’s O(32) per number. Bit tricks are covered on the bit manipulation page.

Complexity

	Time	Extra memory
Insert, search, startsWith	O(L)	O(L) new nodes at most
Build from n words, total length N	O(N)	O(N) nodes
Search with dots	O(L) to O(26^dots · L)	O(L) call stack
Word Search II, m·n grid, length L	O(m·n · 3^L) worst case	O(N) for the trie

With 26-slot arrays, each node costs 26 pointers, so memory is O(26 · N). That’s usually the first thing to mention when asked about the cost of a trie.

Say this out loud

I’ll store the words in a trie. Each node is a prefix, with up to 26 children and a flag for a word end. Insert and search walk one node per letter, so each is O(L), whatever the number of words. startsWith is the same walk without the flag check.

Interview questions

Interviewer asksWhy use a trie instead of a hash set of all prefixes?

A hash set of every prefix also answers startsWith in O(L). But a word of length L has L prefixes, and storing each as its own string costs O(L²) memory per word. A trie shares those prefixes as nodes, so a word costs at most L nodes. It also supports walks a set can’t do, such as wildcards, or listing every word under a prefix.

Interviewer asksHow do you delete a word from a trie?

Walk to its last node and clear is_word. To free memory too, walk back up, removing each node that now has no children and doesn’t end another word. A recursive delete does this on the way back: it returns true when the child it visited can be removed.

Interviewer asksIn Word Search II, why does the trie make it faster than one search per word?

With one search per word, the grid is searched w times. Words that share a prefix redo the same first steps each time. With a trie, a single DFS from each cell follows every word at once. A path stops when no word continues it. Removing found words and empty leaves keeps cutting branches as the answer fills up.

Practice

10 problems on LeetCode: 1 easy, 7 medium, 2 hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Three of these are solved step by step on this site, as part of the Blind 75: Implement Trie (Prefix Tree), Design Add and Search Words Data Structure and Word Search II.

Recap

Use it when the question is about prefixes, autocomplete, wildcards, or searching many words at once.
A node is a prefix: children by letter, and an is_word flag.
search needs the path and the flag. startsWith needs only the path.
Trie + DFS: walk the trie alongside the search, and stop when no child matches.
Cost: O(L) per operation, whatever the number of words. Memory is O(N) nodes, times 26 with arrays.