Tries

A tree of letters where every shared prefix is stored once — prefix questions in O(length of the word).

intermediate~70 min8 simulations8 problems

▶ guided lesson ⚡ 1-minute summary ↻ 15 recall cards

before this: Tree Recursion · Hashing · Recursion

Section

01 · why it exists

Why this exists, and the weight it carries

since1959–60

Trie (prefix tree)

René de la Briandais; Edward Fredkin (who named it)

In March 1959 René de la Briandais presented "File searching using variable length keys": store keys letter by letter in a tree, so a lookup reads one letter per level. In September 1960 Edward Fredkin independently described the same idea in "Trie Memory" (Communications of the ACM) and coined the name from re-trie-val. Fredkin meant it to be said like "tree"; many people say "try" to keep the two apart.

the problem it solvedLooking up keys of different lengths — words, codes — in time that depends on the key's length, not on how many keys are stored.

its jobs today

Autocomplete and typeahead: walk to the typed prefix, then read precomputed suggestions from that node.
Spell checkers and word games: explore only the letter paths that real words use.
Prefix routing and dictionaries keyed by strings or bits, often as compressed (radix) tries.

the weight it carries

Illustrative: 10 lakh (1,000,000) stored names and the user has typed "pri". Trie: 3 steps to the prefix node, whatever the number of names. HashSet<String>: a prefix has no bucket, so up to 1,000,000 startsWith checks. Sorted array or TreeSet: ⌈log₂ 1,000,000⌉ = 20 string comparisons to find the first match.

without it

Every keystroke in a search box would rescan the whole list, or need a sorted copy plus a binary search per prefix.

when · why · how

when: Many prefix questions over one set of strings: startsWith, autocomplete, shortest root, many words on one board, wildcard search.
why: Each query costs O(L) for an L-letter prefix, independent of N. The price is memory: up to one node per stored letter, 26 child slots each with Node[26].
how: class Node { Node[] children = new Node[26]; boolean isEnd; } — index with ch - 'a'; switch to HashMap<Character, Node> for big or unknown alphabets.

since1968

Binary trie (bitwise trie)

Donald R. Morrison (PATRICIA)

Fredkin's tries branch on letters; the same idea works on the bits of a key. In 1968 Donald R. Morrison published PATRICIA ("Practical Algorithm To Retrieve Information Coded in Alphanumeric") in the Journal of the ACM. NIST describes a Patricia tree as a trie in which every only child is merged into its parent, and a radix tree as a binary Patricia tree. The max-XOR trie in this chapter is the plain, uncompressed version: 31 levels, one per bit.

the problem it solvedStoring and searching keys bit by bit, so lookups cost the key's length in bits and runs of single-child nodes need not be stored.

its jobs today

Maximum-XOR queries: pick the opposite bit at every level, highest bit first.
IP routing: an address is matched against route prefixes bit by bit; the Linux kernel's routing table (fib_trie) is a compressed trie of that kind.

the weight it carries

Illustrative: LC 421's limit, n = 2·10⁵ numbers. All pairs: n(n − 1)/2 = 19,999,900,000 ≈ 2·10¹⁰ XORs. Binary trie: 31 steps to insert + 31 to query per number = 62 × 200,000 = 12,400,000 steps — about 1,600× fewer.

without it

Max-XOR and other "closest by bits" questions fall back to checking every pair: O(n²).

when · why · how

when: XOR maximisation over pairs or queries, or matching keys bit by bit (longest prefix of an address).
why: Each number is a fixed 31-bit path, so insert and query are O(31) = O(1) per number. Greedy works because bit b outweighs all lower bits together (2ᵇ > 2ᵇ − 1).
how: Node[] child = new Node[2]; read bit b with (num >> b) & 1 for b = 30 down to 0.

since?

Trie-guided backtracking (many words at once)

No single inventor: it is a trie's prefix check used to cut a backtracking search short — a standard combination in word-game solvers and in problems like Word Search II.

its jobs today

Word games and puzzle solvers: find every dictionary word on a letter board in one search.
Spell suggestions: walk the dictionary trie while allowing a few edits, and drop any branch with no word left below it.

the weight it carries

Illustrative: LC 212's limits — a 12 × 12 board and 30,000 words. Word Search I per word starts 30,000 × 144 = 4,320,000 searches. With a trie: 144 searches in total, one per start cell, each cut off as soon as its prefix leaves the trie.

without it

Multi-word search would repeat the same board exploration once for every word.

when · why · how

when: Many patterns against one board or text, where most paths die after a few letters.
why: Shared prefixes are explored once for all words, and a missing child prunes the branch for every word together. The worst case is still exponential in word length; real boards collapse fast.
how: Store String word on end nodes, mark visited cells with '#', restore them after the DFS, set node.word = null once found, and trim leaves that hold no word.

02 · plain english

The idea in 30 seconds

A trie (prefix tree) stores words letter by letter: each edge is a letter, each root-to-node path spells a prefix.

Words that share a beginning share the same path, so "car", "card" and "care" reuse the nodes c → a → r.

Any lookup walks one node per letter: O(L) for a word of length L, no matter if you stored 10 words or 10 million.

picture this

Your phone's contact search: type "Pr" and the list instantly narrows to Pradeep, Pranav and Priya. Nothing scans every contact — each letter you type is one step down a path those names share.

03 · remember

What you must know

The root is empty. A node is reached by a path of letters; the node itself stands for that prefix.
An end-of-word flag (isEnd) is essential: without it you can't tell the stored word "app" from the mere prefix of "apple".
search(word) = the path exists and isEnd is true. startsWith(prefix) = the path exists. Same walk, different final check.
Children as Node[26] = fastest and simplest for lowercase a–z, but every node pays for 26 slots. HashMap<Character, Node> = only the letters that exist, any alphabet, slower constant.
Add counters for free superpowers: pass (words through this node) answers "how many words start with p?" in O(L), and makes delete easy.
Autocomplete = walk to the prefix node, then DFS its subtree. Visiting children a→z returns results already sorted. For top-k suggestions, store the k best words on each node at insert time.
A wildcard . turns search into a DFS that branches only at the dots; normal letters still follow one child.
Tries aren't only for letters: a binary trie stores numbers bit by bit (high bit first) and answers max-XOR queries greedily.
Many words + one grid (Word Search II) → put the words in a trie and let it prune the DFS: stop as soon as no word has the current prefix.
When the match runs backwards, insert the words reversed — Palindrome Pairs reads one word forwards down a trie of reversed words.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Insert words — shared prefixes reuse nodes

New letters grow new branches; known prefixes are walked, not copied. Boxes mark where a word ends.

loading simulation…

javajava.util.*

1class Trie {2    private static class Node {3        Node[] children = new Node[26]; // one slot per letter 'a'..'z'4        boolean isEnd;                  // true if a word ends exactly here5    }6 7    private final Node root = new Node();8 9    public void insert(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            int i = ch - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isEnd = true;17    }18 19    public boolean search(String word) {20        Node node = walk(word);21        return node != null && node.isEnd;22    }23 24    public boolean startsWith(String prefix) {25        return walk(prefix) != null;26    }27 28    /** Follows s letter by letter; null as soon as a letter is missing. */29    private Node walk(String s) {30        Node cur = root;31        for (char ch : s.toCharArray()) {32            cur = cur.children[ch - 'a'];33            if (cur == null) return null;34        }35        return cur;36    }37}

sim

search(word) vs startsWith(prefix)

Both walk the same path. Only search also demands the end-of-word box at the last letter.

loading simulation…

javajava.util.*

1class Trie {2    private static class Node {3        Node[] children = new Node[26]; // one slot per letter 'a'..'z'4        boolean isEnd;                  // true if a word ends exactly here5    }6 7    private final Node root = new Node();8 9    public void insert(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            int i = ch - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isEnd = true;17    }18 19    public boolean search(String word) {20        Node node = walk(word);21        return node != null && node.isEnd;22    }23 24    public boolean startsWith(String prefix) {25        return walk(prefix) != null;26    }27 28    /** Follows s letter by letter; null as soon as a letter is missing. */29    private Node walk(String s) {30        Node cur = root;31        for (char ch : s.toCharArray()) {32            cur = cur.children[ch - 'a'];33            if (cur == null) return null;34        }35        return cur;36    }37}

sim

Counting trie — count prefixes, erase, prune

Each node shows how many words pass through it. Erase decrements; when a count hits 0 the whole branch is cut.

loading simulation…

javajava.util.*

1class CountingTrie {2    private static class Node {3        Node[] children = new Node[26];4        int pass; // how many stored words go through this node5        int end;  // how many stored words end exactly here6    }7 8    private final Node root = new Node();9 10    void insert(String word) {11        Node cur = root;12        cur.pass++;13        for (char ch : word.toCharArray()) {14            int i = ch - 'a';15            if (cur.children[i] == null) cur.children[i] = new Node();16            cur = cur.children[i];17            cur.pass++;18        }19        cur.end++;20    }21 22    int countWordsEqualTo(String word) {23        Node node = walk(word);24        return node == null ? 0 : node.end;25    }26 27    int countWordsStartingWith(String prefix) {28        Node node = walk(prefix);29        return node == null ? 0 : node.pass;30    }31 32    /** Removes one copy of word (if stored) and frees branches no word uses any more. */33    void erase(String word) {34        if (countWordsEqualTo(word) == 0) return;35        Node cur = root;36        cur.pass--;37        for (char ch : word.toCharArray()) {38            int i = ch - 'a';39            Node next = cur.children[i];40            if (--next.pass == 0) {41                cur.children[i] = null;42                return; // nothing below was used by any other word43            }44            cur = next;45        }46        cur.end--;47    }48 49    private Node walk(String s) {50        Node cur = root;51        for (char ch : s.toCharArray()) {52            cur = cur.children[ch - 'a'];53            if (cur == null) return null;54        }55        return cur;56    }57}

sim

Autocomplete — DFS below the prefix node

Everything outside the prefix's subtree stays grey: it is never touched.

loading simulation…

javajava.util.*

1class Autocomplete {2    private static class Node {3        Node[] children = new Node[26];4        boolean isEnd;5    }6 7    private final Node root = new Node();8 9    void insert(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            int i = ch - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isEnd = true;17    }18 19    /** Every stored word that starts with prefix, in alphabetical order. */20    List<String> complete(String prefix) {21        List<String> out = new ArrayList<>();22        Node cur = root;23        for (char ch : prefix.toCharArray()) {24            cur = cur.children[ch - 'a'];25            if (cur == null) return out;26        }27        collect(cur, new StringBuilder(prefix), out);28        return out;29    }30 31    /** DFS below the prefix node. Visiting 'a'..'z' in order gives sorted output for free. */32    private void collect(Node node, StringBuilder path, List<String> out) {33        if (node.isEnd) out.add(path.toString());34        for (int i = 0; i < 26; i++) {35            if (node.children[i] == null) continue;36            path.append((char) ('a' + i));37            collect(node.children[i], path, out);38            path.deleteCharAt(path.length() - 1);39        }40    }41}

sim

Wildcard search — branch only at the dots

A letter follows exactly one child; a '.' tries the children one by one. Grey nodes are branches that failed.

loading simulation…

javajava.util.*

1class WordDictionary {2    private static class Node {3        Node[] children = new Node[26];4        boolean isEnd;5    }6 7    private final Node root = new Node();8 9    public void addWord(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            int i = ch - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isEnd = true;17    }18 19    public boolean search(String pattern) {20        return dfs(pattern, 0, root);21    }22 23    private boolean dfs(String pattern, int i, Node node) {24        if (i == pattern.length()) return node.isEnd;   // used every character25        char ch = pattern.charAt(i);26        if (ch == '.') {                                // wildcard: try every child27            for (Node child : node.children) {28                if (child != null && dfs(pattern, i + 1, child)) return true;29            }30            return false;                               // no child led to a word31        }32        Node next = node.children[ch - 'a'];            // normal letter: one path only33        return next != null && dfs(pattern, i + 1, next);34    }35}

sim

Search suggestions — a top-3 list on every node

Products go in sorted, so the first 3 words through a node are its 3 smallest. Typing is then one step per letter.

loading simulation…

javajava.util.*

1class Solution {2    private static class Node {3        Node[] children = new Node[26];4        List<String> top = new ArrayList<>(3); // first 3 words (alphabetically) below this node5    }6 7    public List<List<String>> suggestedProducts(String[] products, String searchWord) {8        String[] sorted = products.clone();9        Arrays.sort(sorted);                    // insert in order → first 3 seen are the smallest10        Node root = new Node();11        for (String p : sorted) {12            Node cur = root;13            for (char ch : p.toCharArray()) {14                int i = ch - 'a';15                if (cur.children[i] == null) cur.children[i] = new Node();16                cur = cur.children[i];17                if (cur.top.size() < 3) cur.top.add(p);18            }19        }20        List<List<String>> result = new ArrayList<>();21        Node cur = root;22        for (char ch : searchWord.toCharArray()) {23            cur = (cur == null) ? null : cur.children[ch - 'a'];24            result.add(cur == null ? new ArrayList<>() : cur.top); // dead end stays dead25        }26        return result;27    }28}

sim

Word Search II — a trie steering a grid DFS

One DFS hunts all words at once. Red = pruned (no word continues this way). Finished branches are trimmed from the trie.

loading simulation…

javajava.util.*

1class Solution {2    private static class Node {3        Node[] children = new Node[26];4        String word; // the full word that ends here (null if none)5    }6 7    public List<String> findWords(char[][] board, String[] words) {8        Node root = new Node();9        for (String w : words) {10            Node cur = root;11            for (char ch : w.toCharArray()) {12                int i = ch - 'a';13                if (cur.children[i] == null) cur.children[i] = new Node();14                cur = cur.children[i];15            }16            cur.word = w;17        }18        List<String> found = new ArrayList<>();19        for (int r = 0; r < board.length; r++)20            for (int c = 0; c < board[0].length; c++)21                dfs(board, r, c, root, found);22        return found;23    }24 25    private void dfs(char[][] board, int r, int c, Node parent, List<String> found) {26        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return;27        char ch = board[r][c];28        if (ch == '#') return;29        Node node = parent.children[ch - 'a'];30        if (node == null) return;31        if (node.word != null) {32            found.add(node.word);33            node.word = null; // report each word only once34        }35        board[r][c] = '#';36        dfs(board, r + 1, c, node, found);37        dfs(board, r - 1, c, node, found);38        dfs(board, r, c + 1, node, found);39        dfs(board, r, c - 1, node, found);40        board[r][c] = ch;41        if (node.word == null && isLeaf(node)) parent.children[ch - 'a'] = null;42    }43 44    private boolean isLeaf(Node node) {45        for (Node child : node.children) if (child != null) return false;46        return true;47    }48}

sim

Binary trie — maximum XOR, one bit at a time

For every bit, try to go the opposite way: a 1 in a higher bit is worth more than all lower bits together.

loading simulation…

javajava.util.*

1class Solution {2    private static final int HIGH_BIT = 30; // nums[i] < 2^31, so bit 30 is the top bit3    private static class Node {4        Node[] child = new Node[2]; // child[0] = bit 0, child[1] = bit 15    }6 7    public int findMaximumXOR(int[] nums) {8        Node root = new Node();9        int best = 0;10        for (int num : nums) {11            insert(root, num);12            best = Math.max(best, bestPartner(root, num));13        }14        return best;15    }16 17    private void insert(Node root, int num) {18        Node cur = root;19        for (int b = HIGH_BIT; b >= 0; b--) {20            int bit = (num >> b) & 1;21            if (cur.child[bit] == null) cur.child[bit] = new Node();22            cur = cur.child[bit];23        }24    }25 26    /** Largest num ^ x over every x already stored (num itself is stored, so the answer is ≥ 0). */27    private int bestPartner(Node root, int num) {28        Node cur = root;29        int xor = 0;30        for (int b = HIGH_BIT; b >= 0; b--) {31            int bit = (num >> b) & 1;32            int want = bit ^ 1;33            if (cur.child[want] != null) {34                xor |= 1 << b;35                cur = cur.child[want];36            } else {37                cur = cur.child[bit];38            }39        }40        return xor;41    }42}

05 · cost

Time & space, explained

Trie operations (L = length of the word/prefix, S = total letters stored, Σ = alphabet size)
	Time	Extra space	why
insert(word)	O(L)	O(L) worst	One step per letter; at most L new nodes when no prefix is shared.
search(word)	O(L)	O(1)	Walk at most L edges, then check one flag. The number of stored words never appears.
startsWith(prefix)	O(L)	O(1)	The same walk as search, without the final flag check.
search with k wildcards	O(Σᵏ · L) worst	O(L)	Each '.' may fan out to Σ = 26 children; letters never branch. Never more than the nodes in the trie.
countWordsStartingWith(prefix)	O(L)	O(1)	With a `pass` counter on every node, the answer is stored at the prefix node.
erase(word) (counting trie)	O(L)	O(1)	Walk once, decrement counters, cut the branch where a counter hits 0.
autocomplete(prefix)	O(L + K)	O(depth)	L to reach the prefix node, then K = nodes in its subtree (plus output); recursion depth = longest word.
Build from N words	O(S)	O(S·Σ) array / O(S) map	At most S + 1 nodes. Each array node always holds Σ = 26 references, even if empty.

Trie vs the alternatives for N words
	contains(word)	any word starts with p?	Memory	why
HashSet<String>	O(L) average	O(N·L)	O(S)	Hashing a word costs O(L), but a prefix has no hash bucket — you must scan every word.
TreeSet<String> / sorted array	O(L log N)	O(L log N)	O(S)	`ceiling(p)` finds the first word ≥ p in log N comparisons, each up to L chars.
Trie with Node[26]	O(L)	O(L)	O(S·26)	Fastest walk: array index per letter. Pays 26 slots per node, used or not.
Trie with HashMap children	O(L) average	O(L) average	O(S), bigger constant	Only existing letters are stored, but each map entry has object overhead (boxed Character, entry, table).

06 · java

Raw vs Collections Framework

Children: Node[26] array vs HashMap

javaNode[26] — lowercase a–zjava.util.*

1class Trie {2    private static class Node {3        Node[] children = new Node[26]; // one slot per letter 'a'..'z'4        boolean isEnd;                  // true if a word ends exactly here5    }6 7    private final Node root = new Node();8 9    public void insert(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            int i = ch - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isEnd = true;17    }18 19    public boolean search(String word) {20        Node node = walk(word);21        return node != null && node.isEnd;22    }23 24    public boolean startsWith(String prefix) {25        return walk(prefix) != null;26    }27 28    /** Follows s letter by letter; null as soon as a letter is missing. */29    private Node walk(String s) {30        Node cur = root;31        for (char ch : s.toCharArray()) {32            cur = cur.children[ch - 'a'];33            if (cur == null) return null;34        }35        return cur;36    }37}

javaHashMap<Character, Node> — any alphabetjava.util.*

1class MapTrie {2    private static class Node {3        Map<Character, Node> children = new HashMap<>(); // only letters that exist4        boolean isEnd;5    }6 7    private final Node root = new Node();8 9    public void insert(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            cur = cur.children.computeIfAbsent(ch, k -> new Node());13        }14        cur.isEnd = true;15    }16 17    public boolean search(String word) {18        Node node = walk(word);19        return node != null && node.isEnd;20    }21 22    public boolean startsWith(String prefix) {23        return walk(prefix) != null;24    }25 26    private Node walk(String s) {27        Node cur = root;28        for (char ch : s.toCharArray()) {29            cur = cur.children.get(ch);30            if (cur == null) return null;31        }32        return cur;33    }34}

ch - 'a' turns a letter into an index 0..25 — no hashing, no boxing. This is the interview default when the input is lowercase a–z.
computeIfAbsent(ch, k -> new Node()) gets the child or creates it in one call — the map version of "if null, create".
Use the map version for Unicode, mixed case, digits, or very sparse tries (most nodes have one or two children).
Want children in sorted order with a map? Use TreeMap<Character, Node> — O(log Σ) per step, but iteration is alphabetical.
Java has no built-in trie class. You will always write the ~25 lines yourself — practise until it takes 3 minutes.

Counting trie — prefix counts and delete

javapass / end countersjava.util.*

1class CountingTrie {2    private static class Node {3        Node[] children = new Node[26];4        int pass; // how many stored words go through this node5        int end;  // how many stored words end exactly here6    }7 8    private final Node root = new Node();9 10    void insert(String word) {11        Node cur = root;12        cur.pass++;13        for (char ch : word.toCharArray()) {14            int i = ch - 'a';15            if (cur.children[i] == null) cur.children[i] = new Node();16            cur = cur.children[i];17            cur.pass++;18        }19        cur.end++;20    }21 22    int countWordsEqualTo(String word) {23        Node node = walk(word);24        return node == null ? 0 : node.end;25    }26 27    int countWordsStartingWith(String prefix) {28        Node node = walk(prefix);29        return node == null ? 0 : node.pass;30    }31 32    /** Removes one copy of word (if stored) and frees branches no word uses any more. */33    void erase(String word) {34        if (countWordsEqualTo(word) == 0) return;35        Node cur = root;36        cur.pass--;37        for (char ch : word.toCharArray()) {38            int i = ch - 'a';39            Node next = cur.children[i];40            if (--next.pass == 0) {41                cur.children[i] = null;42                return; // nothing below was used by any other word43            }44            cur = next;45        }46        cur.end--;47    }48 49    private Node walk(String s) {50        Node cur = root;51        for (char ch : s.toCharArray()) {52            cur = cur.children[ch - 'a'];53            if (cur == null) return null;54        }55        return cur;56    }57}

pass answers "how many words start with p" without visiting the subtree; end supports duplicates.
Delete is the classic trap: don't just clear isEnd — counters tell you exactly which nodes no longer serve any word, so you can cut them.
Cutting one reference (children[i] = null) frees the whole branch; the garbage collector does the rest.

Autocomplete — collect words under a prefix

javawalk + DFS with a StringBuilderjava.util.*

1class Autocomplete {2    private static class Node {3        Node[] children = new Node[26];4        boolean isEnd;5    }6 7    private final Node root = new Node();8 9    void insert(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            int i = ch - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isEnd = true;17    }18 19    /** Every stored word that starts with prefix, in alphabetical order. */20    List<String> complete(String prefix) {21        List<String> out = new ArrayList<>();22        Node cur = root;23        for (char ch : prefix.toCharArray()) {24            cur = cur.children[ch - 'a'];25            if (cur == null) return out;26        }27        collect(cur, new StringBuilder(prefix), out);28        return out;29    }30 31    /** DFS below the prefix node. Visiting 'a'..'z' in order gives sorted output for free. */32    private void collect(Node node, StringBuilder path, List<String> out) {33        if (node.isEnd) out.add(path.toString());34        for (int i = 0; i < 26; i++) {35            if (node.children[i] == null) continue;36            path.append((char) ('a' + i));37            collect(node.children[i], path, out);38            path.deleteCharAt(path.length() - 1);39        }40    }41}

One shared StringBuilder: append before going down, deleteCharAt after coming back — the backtracking pattern.
Looping i = 0..25 visits children alphabetically, so results come out sorted with no extra sort.
For "top 3 suggestions" store the best 3 words on every node at insert time (see LC 1268) — queries become O(L).

Java API you will actually use
call	does	cost
`new Node[26]`	Child slots for 'a'..'z'; all start as null	O(26) to allocate
`ch - 'a'`	Letter → index 0..25 (char arithmetic)	O(1)
`(char) ('a' + i)`	Index → letter, when rebuilding words in a DFS	O(1)
`map.computeIfAbsent(ch, k -> new Node())`	Get the child, creating it if missing	O(1) average
`map.get(ch)`	Child or null	O(1) average
`new TreeMap<Character, Node>()`	Children kept in sorted order	O(log Σ) per step
`sb.append(c) / sb.deleteCharAt(sb.length() - 1)`	Grow / shrink the current path while backtracking	O(1) amortized
`new StringBuilder(w).reverse().toString()`	A word reversed (Palindrome Pairs)	O(L)
`treeSet.ceiling(prefix)`	First stored string ≥ prefix — a trie-free prefix check	O(L log N)
`(num >> b) & 1`	Bit b of num (binary trie)	O(1)

Many prefix queries on a fixed set of words

→ Trie (Node[26])

Every query is O(L), independent of N.

Only exact lookups ("is this word in the set?")

→ HashSet<String>

Simpler and less memory; a trie buys you nothing here.

Unicode / large or unknown alphabet

→ Trie with HashMap children

A 65,536-slot array per node would be absurd.

A few prefix queries, memory matters

→ Sorted array / TreeSet + binary search

No per-node overhead; O(L log N) per query is often fine.

Max XOR / bitwise "closest" numbers

→ Binary trie (2 children)

Greedy bit-by-bit choice from the highest bit.

Find many words in a grid or text

→ Trie + DFS (or Aho–Corasick for text)

One traversal serves all words and prunes dead prefixes.

07 · recognise

Spot the pattern

"prefix", "starts with", "autocomplete", "suggestions", "typeahead"

Trie — walk to the prefix node

Search many words at once in a grid or a string

Put all words in a trie, run one DFS that follows the trie

Wildcards like . matching any letter

Trie + DFS that branches only at the wildcard

Replace words by their shortest root / dictionary prefix

Trie: stop at the first end-of-word node on the walk

Maximize XOR of pairs, or XOR queries against a set

Binary trie, highest bit first, greedily take the opposite bit

"Built one character at a time", "every prefix is also a word"

Trie DFS that only enters end-of-word nodes

Count words with a given prefix, with inserts and deletes

Counting trie (pass / end counters)

Two strings joined must form a palindrome, or match end-to-start

Trie (or HashMap) of the words reversed

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Forgetting isEnd: then search("app") returns true after inserting only "apple".
Returning true from search just because the walk finished — the final node must also be an end of word.
Deleting by clearing isEnd but leaving dead branches: startsWith still says yes for a prefix no word has.
Using Node[26] when the input has uppercase, digits or spaces — ch - 'a' goes negative or past 25 → ArrayIndexOutOfBoundsException.
Wildcard search: returning the result of the first child at a '.', instead of trying the next child when it fails.
Word Search II: forgetting to un-mark the cell after the DFS, or reporting the same word twice (clear the stored word once found).
Binary trie: walking bits from low to high. Greedy only works from the highest bit down.
Building the whole trie when you only need one exact lookup — a HashSet is simpler and lighter.

tricks

Write the node class first and say it out loud: "children plus an end flag". Everything else follows.
Factor out a walk(s) helper that returns the node or null; search and startsWith become one line each.
In word problems, store the whole word on its end node (String word) instead of a boolean — no need to rebuild it from the path.
Mention the memory trade-off unprompted: "26 references per node; with a map I'd only pay for existing letters." It signals depth.
If the interviewer asks for top-k suggestions, keep a small sorted list on each node at insert time instead of DFS at query time.
Chalo, dry-run karte hain — with 3 words that share a prefix ("car", "card", "cat"). It exposes most trie bugs.

09 · why & how

Questions you might be too shy to ask

Where is the letter actually stored? And why is the root empty?

With Node[26], the letter isn't stored as a value at all — it is the slot number. children[2] != null means "there is an edge for 'c' here". The root stands for the empty prefix "", so words starting with different letters can all hang under one starting point. So the path root → c → a → t spells "cat"; each node is "the prefix so far".

Why does ch - 'a' give me a number?

In Java a char is a small number underneath: 'a' is 97, 'b' is 98, 'c' is 99. Subtracting two chars gives an int, so 'c' - 'a' is 2 — the slot for 'c'. Going back: (char) ('a' + 2) is 'c'. This only works because 'a'..'z' are consecutive numbers.

Why is a trie lookup O(L) and not O(log N) like a balanced tree?

A BST compares whole words at each node, and it has log N levels. A trie consumes one letter per level, and the number of levels is the length of the word. Ten words or ten million — a 5-letter lookup takes 5 steps.

Why is the Node class static?

A nested class without static secretly keeps a reference to the outer Trie object inside every node. A trie can have lakhs of nodes, so that's wasted memory for nothing — a node never needs the outer object. private static class Node is a plain small class that just lives inside Trie. Use it for TreeNode-style helpers too.

Isn't a HashSet also O(L)? Why bother with a trie?

For exact lookups, yes — a HashSet is usually the better choice. The trie wins as soon as prefixes matter: a HashSet has no way to answer "does any word start with 'ap'?" without scanning all N words.

Can't I just put every prefix of every word in a HashSet?

You can — startsWith becomes one O(L) lookup. But "apple" alone adds 5 strings (a, ap, app, appl, apple): 15 characters for a 5-letter word. That is O(L²) time and memory per word, where a trie needs O(L). And the set still can't list the words under a prefix (autocomplete). Fine for small inputs; say the trade-off.

What happens if I insert the same word twice?

With a boolean isEnd, nothing changes: the walk finds every node already there and sets a flag that is already true. If duplicates must be counted, use an int end counter and do end++ instead (the counting trie in the Java section).

How much memory does a trie really use?

At most S + 1 nodes for S total letters (fewer when prefixes are shared). With Node[26], each node holds 26 references (~104–208 bytes in Java on top of the object header), even if only one is used. For sparse data that is wasteful — use a HashMap per node, or a compressed (radix) trie that merges single-child chains.

Array or HashMap for children in an interview?

If the problem says lowercase English letters, use Node[26] — it's shorter, faster and expected. Switch to a map for big or unknown alphabets, and say why.

How do I delete a word correctly?

Keep a pass counter on each node (and end for words ending there). Walk the word decrementing pass; if you reach the last node, decrement its end too. The first node whose counter hits 0 is used by no other word, so cut the link to it and stop — everything below disappears with it. Without counters, use a recursive delete that removes a child only if it has no children and isn't an end of word.

Why does Word Search II need a trie when Word Search I didn't?

Word Search I looks for one word. With W words, running Word Search I W times repeats the same board exploration W times. A trie of all words lets one DFS follow every word's prefix at once and stop the moment no word continues that way.

What is a binary trie, and why does greedy work for maximum XOR?

It stores each number as a path of bits, highest bit first. To maximize a ^ b, you want bit 30 of the result to be 1 if at all possible, because 2³⁰ is bigger than all lower bits added together (2³⁰ − 1). So at each level take the opposite bit if that child exists — a local choice that can never be beaten later.

Max XOR: why start at bit 30 and not bit 31?

The numbers are non-negative ints, so they are below 2³¹. Bit 31 is the sign bit, and it is 0 for all of them. Two zeros XOR to 0, so that level would never help. Bit 30 is the highest bit that can actually differ. If negative numbers were allowed, you would need bit 31 too — and to treat it with care.

Palindrome Pairs feels impossible. Where do I start?

With the condition, not the code. Say words[i] + words[j] is a palindrome and words[i] is the longer one. Then the beginning of words[i] is words[j] backwards, and the leftover part of words[i] reads the same both ways. (When words[j] is longer, flip it: the end of words[j] is words[i] backwards.) So store every word reversed (in a HashMap or a trie) and look up pieces of words[i] in it. Brute force first, then this — interviewers mostly want to see that reasoning.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#208
Implement Trie (Prefix Tree)must-do
MediumAppleOracleMicrosoftAmazonGoogle+1
#211
Design Add and Search Words Data Structuremust-do
MediumByteDance / TikTokAmazonAppleMicrosoftMeta+1
#212
Word Search IImust-do
HardUberAirbnbByteDance / TikTokAmazonMicrosoft+1
#648
Replace Words
MediumByteDance / TikTokMicrosoftGoogle
#1268
Search Suggestions Systemmust-do
MediumAmazonOracleAdobeGoogleMeta
#421
Maximum XOR of Two Numbers in an Array
MediumBloomberg
#720
Longest Word in Dictionary
MediumMicrosoftAmazon
#336
Palindrome Pairs
HardAirbnbGoogleAmazon

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#14
Longest Common Prefix
Easyin Arrays & Strings
The common prefix is the trie's single lane from the root — try its trie approach, then compare it with the simpler column scan.

11 · revise

The whole chapter on one screen

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

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.
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.
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;
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].
trap
search must check isEnd at the last node — otherwise "app" is "found" after inserting only "apple".
trap
ch - 'a' assumes lowercase a–z. Uppercase, digits or spaces give an index outside 0..25 → ArrayIndexOutOfBoundsException. Use a HashMap per node.
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.
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.
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).

12 · recall

Flip, remember, repeat

card 1 / 15

recall

What does one trie node hold, and what does a node stand for?

tap or Space to flip ↻

Question 1: What does one trie node hold, and what does a node stand for?

13 · check yourself

Quick quiz

You insert only "apple". What do search("app") and startsWith("app") return?
A trie stores 1 million words. How many steps does search("hello") take?
When is `HashMap<Character, Node>` children a better choice than `Node[26]`?
WordDictionary holds "bad", "bat" and "map". Where does search("b.d") branch?
In Word Search II, what does the trie let the DFS do that running Word Search I per word cannot?
Maximum XOR with a binary trie: why must you walk bits from the highest to the lowest?
In a counting trie, "bat" and "bath" are stored. You erase "bath". What happens?
Autocomplete returns results in alphabetical order without sorting. Why?

0/0 correct · 8 left

14 · learn more