Trie

How a trie works

Each node represents a position in a key (the empty prefix at the root, then one character deeper at each step). A node has up to alphabet-size children, one per possible next character. Following the path from root to any node spells out a prefix.

To mark that "cat" is in the trie:

1. From the root, follow or create the child for 'c'.
2. From that node, follow or create the child for 'a'.
3. From that node, follow or create the child for 't'.
4. Mark the 't' node as isEnd = true.

To search for "cat", walk the same path. If any step has no matching child, the word isn't in the trie. If you reach the end and isEnd is true, it is.

Crucial: isEnd is a separate flag. The path "cat" exists internally even when only "category" is stored — but unless the 't' node is marked, "cat" is just a prefix of something else, not a stored word.

Trie variants

	Standard trie	Compressed trie (radix)	Ternary search trie
Children per node	Up to alphabet size	Variable (collapsed chains)	3 (left/mid/right)
Memory per node	Array or map of children	Edge labels	3 pointers + char
Search	O(L)	O(L)	O(L · log alphabet)
Memory (English dict)	50-100 MB	2-5 MB	10-20 MB
Insert / delete complexity	Simple	Hard (split / merge edges)	Moderate
Best for	Teaching, small alphabets	Production dictionaries	Memory-conscious general use

Real production tries are almost always compressed. Linux's IP routing table is a binary compressed trie — each lookup matches a longest-prefix in O(32) for IPv4 or O(128) for IPv6 regardless of how many routes are configured.

When to use a trie

• Autocomplete and search-as-you-type. Walk the trie with each keystroke; the subtree below the cursor IS the candidate set. No re-scanning required.
• Spell-checking. Generate candidate corrections by walking the trie with edit-distance bounds (Levenshtein automaton on a trie is the standard fast algorithm).
• IP routing. Longest-prefix match: walk the binary trie following the IP address bits; the deepest isEnd-marked node is the matching route. Linux's routing tables, BGP route lookup, all radix tries.
• Word search and Boggle. Build a trie of the dictionary; do DFS on the board pruning whenever the current letters don't match a trie path. Cuts the search space dramatically vs checking every substring against a hash set.
• Phone-number directories and dial-prefix matching. Each digit is a level of the trie; routing rules match by longest dial prefix.

Skip tries for raw key-value lookups on small key counts — a hash table is simpler and typically faster. The trie wins when prefix structure matters or when keys share common prefixes.

JavaScript implementation

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  constructor() { this.root = new TrieNode(); }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }

  search(word) {
    const node = this._walk(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }

  _walk(s) {
    let node = this.root;
    for (const ch of s) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }

  // List all words with a given prefix (autocomplete)
  autocomplete(prefix, limit = 10) {
    const node = this._walk(prefix);
    if (!node) return [];
    const results = [];
    const stack = [[node, prefix]];
    while (stack.length && results.length < limit) {
      const [n, str] = stack.pop();
      if (n.isEnd) results.push(str);
      for (const [ch, child] of n.children) stack.push([child, str + ch]);
    }
    return results;
  }
}

Python implementation

class TrieNode:
    __slots__ = ('children', 'is_end')
    def __init__(self):
        self.children = {}
        self.is_end = False

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 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

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

    def autocomplete(self, prefix, limit=10):
        node = self._walk(prefix)
        if not node: return []
        out = []
        stack = [(node, prefix)]
        while stack and len(out) < limit:
            n, s = stack.pop()
            if n.is_end: out.append(s)
            for ch, child in n.children.items():
                stack.append((child, s + ch))
        return out

Famous trie problems

Word Search II (LeetCode 212)

Given a 2D board of letters and a list of words, find all words that can be formed by adjacent letters on the board. The naive approach checks each word against the board: O(words × cells × word-length). The trie approach: build a trie of the dictionary, then DFS the board pruning whenever the current path isn't a trie prefix. Each board cell now does work proportional only to the maximum word length, with massive pruning.

Longest Word in Dictionary

Given a list of words, find the longest word that can be built one character at a time by other words in the list. BFS the trie level-by-level — at each node, only continue if it's marked isEnd. The deepest marked node is the answer.

Longest-Prefix IP Match

// Binary trie for IPv4 routes
class IPTrie {
  constructor() { this.root = { left: null, right: null, route: null }; }

  add(prefix, prefixLen, route) {
    // prefix is a 32-bit integer; prefixLen is how many bits matter
    let node = this.root;
    for (let i = 31; i >= 32 - prefixLen; i--) {
      const bit = (prefix >> i) & 1;
      const key = bit ? 'right' : 'left';
      if (!node[key]) node[key] = { left: null, right: null, route: null };
      node = node[key];
    }
    node.route = route;
  }

  lookup(ip) {
    // Walk down following IP bits; return the deepest matched route
    let node = this.root;
    let bestRoute = null;
    for (let i = 31; i >= 0 && node; i--) {
      if (node.route !== null) bestRoute = node.route;
      const bit = (ip >> i) & 1;
      node = bit ? node.right : node.left;
    }
    return bestRoute;
  }
}

Common bugs and edge cases

• Forgetting isEnd. Storing "cat" creates internal nodes c → a → t, but unless 't' is marked isEnd, search("cat") returns false. The most common trie bug.
• Using arrays per node when alphabet is large. A 26-element array per node is fine for English. For Unicode (~1M code points), use a hash map or you'll run out of memory.
• Deleting the wrong nodes. When deleting "cat", you must NOT remove nodes shared with other stored words. Walk back from the leaf, removing only nodes that have no children and aren't marked isEnd.
• Case sensitivity confusion. Decide upfront: case-sensitive or case-insensitive. Mixing them produces inconsistent autocomplete (typing "Apple" doesn't surface "apple"). Lowercase on insert and on query is the standard fix.
• Compressed trie split bugs. Inserting "category" into a trie that already has "car" requires splitting the "ar" edge into "ar" + "tegory". Easy to break — the path-compression invariant is fragile. Standard tries are simpler when correctness matters more than memory.