Trie — Prefix Tree for String Sets

Basic structure

class TrieNode {
  TrieNode[] children = new TrieNode[26];
  boolean isEnd;
}
void insert(TrieNode root, String w) {
  TrieNode cur = root;
  for (char c : w.toCharArray()) {
    if (cur.children[c-'a'] == null) cur.children[c-'a'] = new TrieNode();
    cur = cur.children[c-'a'];
  }
  cur.isEnd = true;
}

Autocomplete

Traverse to prefix node. DFS descendants collecting isEnd words. Return top-K by frequency.

Radix / Patricia trie

Compress paths with single child. Saves memory. IP routing tables (CIDR longest prefix match) use radix tries.

Applications

Autocomplete. Spell check. IP routing. Aho-Corasick. Suffix trie/tree.