Tries

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A tree of characters: each edge is a letter, each node a prefix, and an isEnd flag marks where a stored word ends. Shared beginnings are stored once.

   #1
2. ↯use it when

   Prefix questions over one set of strings: startsWith, autocomplete, shortest root, many words on one board, wildcard search — and max XOR with a binary trie.

   #2
3. { }template

   for (char ch : w.toCharArray()) { int i = ch - 'a'; if (cur.children[i] == null) cur.children[i] = new Node(); cur = cur.children[i]; } then cur.isEnd = true;

   #3
4. O( )cost

   insert / search / startsWith = O(L) for an L-letter word, whatever the number of words. Memory: up to one node per stored letter, 26 slots each with Node[26].

   #4
5. !trap

   search must check isEnd at the last node — otherwise "app" is "found" after inserting only "apple".

   #5
6. !trap

   ch - 'a' assumes lowercase a–z. Uppercase, digits or spaces give an index outside 0..25 → ArrayIndexOutOfBoundsException. Use a HashMap per node.

   #6
7. ✦pro tip

   Many words, one board? Build one trie, run one DFS that follows it, prune when no word continues. Store the whole word on its end node.

   #7
8. ✦pro tip

   Max XOR: insert bits 30 → 0 into a binary trie; at each bit take the opposite child if it exists. A higher bit beats all lower bits together.

   #8
9. ✦pro tip

   Top-k suggestions fast: insert words in sorted order and keep the first k on every node — each typed letter is then O(1).

   #9

Shaky on a card? Open the chapter or flip its recall cards.