Skills101

AdvancedData Structures & Algorithms · Lesson 27 of 29 · Updated ·

Tries (Prefix Trees) — Insert, Search, Prefix Count and Autocomplete

When you type "ca" in a phone's contact search, it shows "Carol", "Catherine" and "Cathy" at once. The phone is answering a prefix question: which stored words start with these letters? A hash set can tell you whether one exact word exists, but it cannot answer prefix questions quickly. A trie (say "try", from retrieval), also called a prefix tree, is built exactly for this.

1. What a trie looks like

A trie is a tree where:

  • the root is empty;
  • each edge (or child node) stands for one letter;
  • the path from the root to a node spells a prefix;
  • a node is marked end of word if a stored word finishes there.

Here are the words car, card, care, cat, do, dog:

A trie for car, card, care, cat, do and dog; c-a is shared by four words, d-o by two; nodes where a word ends (r, d, e, t, o, g) are green, and each node shows how many words pass through it

Four words share the path c → a. They are stored once, not four times. Notice that car ends at r, but r still has children (d and e). That is why we need the end-of-word mark: reaching a node does not mean a word ends there.

Each node keeps a map from letter to child node, an end flag, and (for later) a count of how many words pass through it.

class TrieNode:
    def __init__(self):
        self.kids = {}        # letter -> TrieNode
        self.end = False      # does a word end here?
        self.count = 0        # how many words pass through this node

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.kids:
                node.kids[ch] = TrieNode()
            node = node.kids[ch]
            node.count += 1
        node.end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.kids:
                return None
            node = node.kids[ch]
        return node

    def search(self, word):              # exact word stored?
        node = self._walk(word)
        return node is not None and node.end

    def starts_with(self, prefix):       # any word with this prefix?
        return self._walk(prefix) is not None

t = Trie()
for w in ["car", "card", "care", "cat", "do", "dog"]:
    t.insert(w)
print(t.search("car"), t.search("ca"), t.search("cart"))
print(t.starts_with("ca"), t.starts_with("dx"))
True False False
True False

search("ca") is False because no word ends at a, even though the path exists. starts_with("ca") only needs the path.

Cost. Insert, search and starts-with all take O(L) time, where L is the length of the word — no matter how many words are stored. Space is at most the total number of letters across all words, and less when prefixes are shared.

3. Prefix count and autocomplete

Because each node stores count, "how many words start with this prefix?" is just: walk down the prefix and read the count. For autocomplete, walk down the prefix, then do a DFS below that node and collect every word that ends there.

Table: prefix c has 4 words (car, card, care, cat), ca has 4, car has 3 (car, card, care), do has 2 (do, dog), and x has 0

class TrieNode:
    def __init__(self):
        self.kids, self.end, self.count = {}, False, 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.kids.setdefault(ch, TrieNode())
            node.count += 1
        node.end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.kids.get(ch)
            if node is None:
                return None
        return node

    def count_prefix(self, prefix):
        node = self._walk(prefix)
        return node.count if node else 0

    def autocomplete(self, prefix, limit=10):
        node, out = self._walk(prefix), []
        def dfs(n, word):
            if len(out) == limit:
                return
            if n.end:
                out.append(word)
            for ch in sorted(n.kids):      # sorted: alphabetical suggestions
                dfs(n.kids[ch], word + ch)
        if node:
            dfs(node, prefix)
        return out

t = Trie()
for w in ["car", "card", "care", "cat", "do", "dog"]:
    t.insert(w)
print(t.count_prefix("car"), t.count_prefix("d"), t.count_prefix("z"))
print(t.autocomplete("ca"))
print(t.autocomplete("ca", limit=2))
3 2 0
['car', 'card', 'care', 'cat']
['car', 'card']

4. The same trie in Java

For lowercase English words, an array of 26 children is faster than a map: the child for letter c is at index c - 'a'.

public class Main {
    static class Node {
        Node[] kids = new Node[26];
        boolean end;
        int count;
    }

    static Node root = new Node();

    static void insert(String w) {
        Node n = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (n.kids[i] == null) n.kids[i] = new Node();
            n = n.kids[i];
            n.count++;
        }
        n.end = true;
    }

    static Node walk(String s) {
        Node n = root;
        for (char c : s.toCharArray()) {
            n = n.kids[c - 'a'];
            if (n == null) return null;
        }
        return n;
    }

    public static void main(String[] args) {
        for (String w : new String[]{"car", "card", "care", "cat", "do", "dog"}) insert(w);
        Node a = walk("car"), b = walk("ca"), c = walk("dot");
        System.out.println((a != null && a.end) + " " + (b != null && b.end) + " " + (c != null));
        System.out.println(walk("ca").count + " " + walk("do").count);
    }
}
true false false
4 2

The array version uses 26 references per node even when most are empty, so it trades memory for speed. A map per node uses less memory when the alphabet is large (for example, Unicode text).

5. Trie or hash set?

QuestionHash setTrie
Is this exact word stored?O(L) on averageO(L)
How many words start with "ca"?must check every wordO(L)
List words with a prefix in sorted ordercheck and sort every wordDFS below one node
Memoryone entry per wordshared prefixes, but node overhead

Typical trie problems: implement a trie, autocomplete or search suggestions, word search on a grid with many words (put the words in a trie so the DFS can stop early), longest common prefix, and replacing words by their shortest root word.

Common mistakes

  • Treating "the path exists" as "the word exists". Always check the end flag in search.
  • Forgetting to increase count on every node along the path, so prefix counts come out wrong.
  • Using c - 'a' when the input can contain capital letters, digits or spaces, which gives a negative or too-large index.
  • Building a trie when the problem only ever asks exact-match questions; a hash set is simpler then.

Quick recap

  • A trie stores words letter by letter; words with a common prefix share one path.
  • Each node has children, an end-of-word flag and, optionally, a pass-through count.
  • Insert, search and starts-with are O(L) for a word of length L.
  • Prefix count: walk the prefix, read count. Autocomplete: walk the prefix, then DFS.
  • Use 26-slot arrays for lowercase letters (fast) or a map per node (flexible).

Practice what you learned

📝 Quiz: Tries (Prefix Trees)5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →