Trie (prefix tree)

You’ll recognise it when

• The question is about prefixes: “does any word start with pre?”, “how many words start with it?”, “suggest words as the user types”.
• You have a dictionary of many words and must match all of them against some text or a letter grid at the same time.
• You need the longest dictionary word that is a prefix of a string, as in a tokenizer or a router matching paths.
• The keys are bit strings and you want the number that differs the most from a given one (maximum XOR).

If you only ever ask “is this exact word in the list?”, a hash set is simpler and just as fast. The trie earns its keep when prefixes matter.

The idea

Think of a paper dictionary with thumb tabs. To find “cart” you open the C section, then the CA pages, then CAR, and each step throws away everything that doesn’t start the same way. “car”, “cat” and “cart” all live behind the same C and CA tabs; nobody prints those letters three times.

A trie is those tabs as a tree. Each edge is one letter, so the path from the root to a node spells a prefix. Words with the same start share the same path, and a flag, is_end, marks the nodes where a whole word stops. To look anything up you spell it from the root, one letter per step. How many other words are stored doesn’t matter.

How it works

Each node holds a map from letter to child and an is_end flag. Scroll through the steps and the graphic follows along: it inserts “car”, “cat”, “cart” and “dog”, then runs four queries.

Why it’s correct: for a non-empty s, the node reached by spelling it exists exactly when some inserted word starts with s, because insert creates the node for every prefix of every word and nothing else creates nodes. is_end on that node is true exactly when s itself was inserted. The empty prefix never leaves the root, which always exists, so starts_with("") is true even in an empty trie; most problems expect exactly that.

class TrieNode:
    def __init__(self):
        self.children = {}       # letter -> TrieNode
        self.is_end = False      # does a whole word end here?


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

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _walk(self, s):
        """The node reached by spelling s from the root, or None."""
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

#include <memory>
#include <string>
#include <unordered_map>
using namespace std;

struct TrieNode {
    unordered_map<char, unique_ptr<TrieNode>> children;   // letter -> child
    bool is_end = false;                                 // does a whole word end here?
};

class Trie {
    unique_ptr<TrieNode> root = make_unique<TrieNode>();

    // The node reached by spelling s from the root, or nullptr.
    TrieNode* walk(const string& s) const {
        TrieNode* node = root.get();
        for (char ch : s) {
            auto it = node->children.find(ch);
            if (it == node->children.end()) return nullptr;
            node = it->second.get();
        }
        return node;
    }

public:
    void insert(const string& word) {
        TrieNode* node = root.get();
        for (char ch : word) {
            auto& child = node->children[ch];
            if (!child) child = make_unique<TrieNode>();
            node = child.get();
        }
        node->is_end = true;
    }

    bool search(const string& word) const {
        TrieNode* node = walk(word);
        return node != nullptr && node->is_end;
    }

    bool starts_with(const string& prefix) const {
        return walk(prefix) != nullptr;
    }
};

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();   // letter -> child
    boolean is_end = false;                                // does a whole word end here?
}

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

    void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                node.children.put(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.is_end = true;
    }

    // The node reached by spelling s from the root, or null.
    private TrieNode walk(String s) {
        TrieNode node = root;
        for (char ch : s.toCharArray()) {
            TrieNode child = node.children.get(ch);
            if (child == null) return null;
            node = child;
        }
        return node;
    }

    boolean search(String word) {
        TrieNode node = walk(word);
        return node != null && node.is_end;
    }

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

Why it’s O(L)

Every operation does one child lookup per letter and stops. For a word of length L that is L steps, whether the trie holds ten words or ten million. A search that falls off early is even cheaper.

The price is memory. The trie has at most one node per inserted letter, so O(total letters), and fewer when prefixes are shared. But every node is an object with its own map or array. A node with a 26-slot array spends 26 pointers even if it has one child, so a trie is often several times bigger than the plain strings. Dictionary children only store the letters that are used, at the cost of hashing each step.

Common mistakes

return node is not None                  # ✗ true for "car" when only "cart" was inserted
return node is not None and node.is_end  # ✓ a whole word ends here

node.children[ch] = TrieNode()           # ✗ wipes out "car" when inserting "cat"
if ch not in node.children:              # ✓ only create what's missing
    node.children[ch] = TrieNode()

Variations

• Counting words with a prefix. Store a counter on each node and add 1 to every node on the insert path. “How many words start with p?” is then a walk plus reading one number.
• Autocomplete. Walk to the prefix’s node, then DFS below it to list the words there. Store the top few suggestions at each node if you need them instantly.
• Word search on a grid. Put all dictionary words in a trie and run one DFS from each cell, walking the trie in step with the path. Abandon a path the moment its letters leave the trie, which prunes almost everything.
• Dict of children vs a 26-slot array. Arrays are faster to index and simpler in C++ and Java, but every node pays for 26 slots. Dicts store only the letters used, which suits large or sparse alphabets like Unicode.
• XOR trie. Insert numbers as bit strings from the highest bit down, with children 0 and 1. To find the stored number with the largest XOR against x, walk down choosing the opposite bit whenever that child exists: O(bits) per query.