Trie Exercises: Practice Problems (with Solutions)
Time to practice tries. Solve each problem yourself first — sketch the trie on paper, trace a small example, and reason about the time and space complexity in terms of word length L and word count n. Only then open the answer sheet. Every View answer link jumps to a full, multi-language solution on the trie solutions page.
How to practice: Set a timer (15–25 min per problem). If you get stuck, re-read the trie operations before peeking. Reuse the
TrieNode(children map +isEnd) from implementing a trie.
Warm-ups
Q1. Implement insert and search. Build a trie supporting insert(word) and search(word) for exact words, plus startsWith(prefix). Each operation should run in O(L) time. This is the foundation for everything else.
Q2. Count words and count prefixes. Augment each node with a counter so you can answer, in O(L): how many stored words exactly equal a string, and how many stored words have a given prefix.
Core problems
Q3. Delete a word from a trie. Implement delete(word) that removes a word if present and prunes any nodes that are no longer part of another word. Be careful not to delete shared prefixes.
Q4. Autocomplete — all words with a prefix. Given a prefix, return every stored word that starts with it. Target O(L + k) where k is the size of the matched subtree.
Q5. Longest common prefix of a set of words. Given a list of strings, return the longest prefix shared by all of them, using a trie. (Walk down while every node has exactly one child and is not a word end.)
Challenge
Q6. Wildcard search with .. Support search(word) where . matches any single character (LeetCode “Add and Search Word”). For a ., you must try every child. State the worst-case complexity.
Q7. Word search in a grid. Given a 2D board of letters and a list of words, return all words that can be formed by adjacent (up/down/left/right) cells without reusing a cell. Use a trie to prune the DFS.
Done? Review every solution on the trie answer sheet — even the ones you solved, since there is often a cleaner approach. Then continue to graphs.