Implement Trie (Prefix Tree)
Understanding the Problem
We need to build a data structure from scratch that supports three operations: inserting a word, searching for an exact word, and checking whether any previously inserted word starts with a given prefix.
A HashSet handles insert and search in O(1), but it has no answer for startsWith. To find whether any stored word begins with a given prefix, you would scan every stored word, which is O(n * m) in the worst case, where n is the number of stored words and m is the average word length.
A Trie removes that scan. It is a tree where each node represents a single character, and paths from the root to nodes spell out prefixes. So startsWith becomes a traversal down the tree, character by character. Words that share a common prefix share the same path in the Trie, so prefix lookups take time proportional to the prefix length, not the number of stored words.
Key Constraints:
1 <= word.length, prefix.length <= 2000-> Words can be fairly long. Our per-operation time complexity should ideally be O(L) where L is the word/prefix length, not dependent on the number of stored words.- Only lowercase English letters -> Each Trie node needs at most 26 children. We can use an array of size 26 for O(1) child lookups.
- At most
3 * 10^4total calls -> Even a brute force approach (scanning all words per query) would be around 3 10^4 2000 = 6 * 10^7 operations, which is borderline. A Trie-based approach runs each operation in O(L) regardless of how many words are stored, keeping things comfortable.
Approach 1: Brute Force (HashSet + Linear Scan for Prefix)
Intuition
Store all inserted words in a list. For insert, append the word. For search, compare against each stored word. For startsWith, scan every stored word and check if any begins with the given prefix.
This ignores the structure of the problem. Every startsWith call examines every stored word, which is wasteful when many words share common prefixes.
Algorithm
- Maintain a list of all inserted words.
- For
insert(word), add the word to the list. - For
search(word), iterate through the list and check for an exact match. - For
startsWith(prefix), iterate through the list and check if any word starts with the prefix.
Example Walkthrough
Input:
Step-by-step: insert "apple", then search "apple" (true), search "app" (false, not inserted), startsWith "app" (true, "apple" starts with "app"), insert "app", search "app" (true).
Code
- Time Complexity: O(n * L) per
searchandstartsWithcall, where n is the number of inserted words and L is the average word length. We scan every word and compare strings.insertis O(1) amortized. - Space Complexity: O(n * L) to store all words, where n is the number of words and L is the average word length.
Search and prefix queries scan every stored word. The next approach pre-computes all prefixes at insert time so prefix lookups become O(1).
Approach 2: HashMap for Words + HashSet for Prefixes
Intuition
Pre-compute all prefixes at insert time. When we insert "apple", we also record "a", "ap", "app", "appl", and "apple" in a set of known prefixes. Then startsWith becomes a single O(1) lookup.
For search, a separate set holds only complete words. This removes the scan entirely: search and prefix queries are O(1) lookups, at the cost of storing every prefix of every word.
Algorithm
- Maintain a HashSet for complete words and a HashSet for all prefixes.
- For
insert(word), add the word to the words set. Also add every prefix of the word (from length 1 to length L) to the prefixes set. - For
search(word), check if the word exists in the words set. - For
startsWith(prefix), check if the prefix exists in the prefixes set.
Example Walkthrough
Code
- Time Complexity: O(L^2) per
insert(creating L substrings costs O(L) each for hashing), O(L) persearchandstartsWith(hash computation is O(L) for a string of length L). - Space Complexity: O(n * L^2) in the worst case, where n is the number of words and L is the maximum word length. Each word of length L generates L prefix strings that need to be stored.
Insert is O(L^2) because we create and hash L separate substrings, and words sharing common prefixes still store duplicate prefix strings. A tree structure stores each shared prefix once, which is what the next approach builds.
Approach 3: Trie (Prefix Tree)
Intuition
This is the structure the problem is asking us to build. A Trie is a tree where each node represents a single character. The root is empty. Each edge from parent to child represents one character. A path from the root to any node spells out a prefix, and we mark certain nodes as "end of word" to distinguish complete words from mere prefixes.
Words that share a prefix share the same path in the tree. "apple" and "app" share the nodes for 'a' -> 'p' -> 'p'. The node for the second 'p' is marked as end-of-word (because "app" is a complete word), and the path continues to 'l' -> 'e' (where "apple" ends). A shared prefix is stored once, no matter how many words pass through it.
This means:
- insert walks down the tree, creating new nodes as needed, and marks the final node as end-of-word.
- search walks down the tree and checks if the final node exists AND is marked as end-of-word.
- startsWith walks down the tree and checks only that the path exists (no end-of-word check needed).
Since each node has at most 26 children (one per lowercase letter), an array of size 26 gives O(1) child access by index.
The difference between search and startsWith is a single check at the end of the traversal. Both walk the same path; search also verifies that the final node is marked isEnd, while startsWith succeeds as long as the path exists.
Algorithm
- Create a TrieNode class with two fields: an array of 26 children (one per letter) and a boolean
isEndflag. - The Trie class holds a reference to the root node (an empty TrieNode).
- For
insert(word): start at the root. For each character, compute its index (char - 'a'). If no child exists at that index, create a new TrieNode. Move to the child node. After processing all characters, mark the current node as end-of-word. - For
search(word): start at the root. For each character, move to the corresponding child. If any child is missing, return false. After traversing all characters, return whether the current node is marked as end-of-word. - For
startsWith(prefix): same traversal as search. If any child is missing, return false. After traversing all characters, return true (we do not care about the end-of-word flag).
Example Walkthrough
Code
- Time Complexity: O(L) for all three operations, where L is the length of the word or prefix. Each operation traverses at most L nodes, doing O(1) work at each node (array index lookup).
- Space Complexity: O(N * 26) in the worst case, where N is the total number of characters across all inserted words. Each character may create a new TrieNode with an array of 26 pointers. In practice, shared prefixes reduce this significantly.