Trie (Prefix Tree)

What is a trie?

A trie (pronounced “try”, from retrieval) is a tree for storing strings. Each edge represents one letter. A word is spelled by the path from the root down to a node marked end-of-word.

Words that begin the same way share the same path. In the model, “car”, “cart” and “care” all go through c → a → r.

Analogy: a paper dictionary’s thumb index. To find “carrot” you go to the C section, then the CA pages, then CAR… Each letter narrows the search.

Structure of a node

Each node stores:

• its children — one per possible next letter (an array of 26, or a hash map),
• an isEnd flag — true if a word finishes here.

The root is empty; it represents the empty prefix.

Operations

Insert(word): start at the root. For each letter, follow the child for that letter — creating it if missing. At the end, set isEnd = true.

Search(word): follow the letters. If any letter is missing → not found. If you reach the end, the answer is the node’s isEnd flag. (That’s why searching “ca” fails even though the path exists: no word ends there.)

StartsWith(prefix): follow the prefix, then collect every word in the subtree below. That’s autocomplete.

Delete(word): unset isEnd, then remove nodes bottom-up that have no children and aren’t the end of another word.

Why is it fast?

Every operation walks one node per letter, so it costs O(L) where L is the word length — independent of how many words are stored. A balanced BST of strings needs O(L · log n) because each comparison of two strings can take L steps.

The cost is memory: each node may hold up to 26 child pointers. Compressed tries (radix trees) merge chains of single children to save space.

Code

class TrieNode:
    def __init__(self):
        self.children = {}      # letter -> TrieNode
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

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

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

    def starts_with(self, prefix):
        node = self._walk(prefix)
        out = []
        def collect(n, acc):
            if n.is_end:
                out.append(acc)
            for ch, child in sorted(n.children.items()):
                collect(child, acc + ch)
        if node:
            collect(node, prefix)
        return out

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

#include <iostream>
#include <string>
using namespace std;

struct Node {
    Node* child[26] = {};
    bool isEnd = false;
};

void insert(Node* root, const string& w) {
    Node* n = root;
    for (char c : w) {
        int i = c - 'a';
        if (!n->child[i]) n->child[i] = new Node();
        n = n->child[i];
    }
    n->isEnd = true;
}

bool search(Node* root, const string& w) {
    Node* n = root;
    for (char c : w) {
        n = n->child[c - 'a'];
        if (!n) return false;
    }
    return n->isEnd;
}

int main() {
    Node* root = new Node();
    for (string w : {"car", "cat", "cart", "care"}) insert(root, w);
    cout << boolalpha << search(root, "cart") << " " << search(root, "ca") << "\n";  // true false
}

Where are tries used?

• Autocomplete and search suggestions as you type.
• Spell checkers and word games (Boggle, Scrabble solvers).
• IP routing: routers find the longest matching address prefix with a binary trie.
• Dictionaries for T9 / phone keyboards.
• Interview problems: “word search II”, “longest common prefix”, “replace words”.

Common mistakes

• Forgetting the isEnd flag, so prefixes are reported as words.
• Using a fixed 26-slot array for non-lowercase input (capitals, digits, Unicode) — use a map instead.
• Ignoring memory: a trie of many unrelated long words can be larger than a hash set.