Implement Trie (Prefix Tree)
Last Updated: March 29, 2026
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.
At first glance, you might think a HashSet could handle this. And it could handle insert and search in O(1). But startsWith is where things get tricky. With a HashSet, you would need to check every stored word to see if any of them begin with the given prefix. That 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 solves this elegantly. It is a tree where each node represents a single character, and paths from the root to nodes spell out prefixes. This means startsWith becomes a simple traversal down the tree, character by character. The key insight is that words sharing 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
The simplest approach: store all words in a list or set. For insert, add the word. For search, check if the word exists. For startsWith, scan through every stored word and check if any of them begin with the given prefix.
This works, but it completely 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.
This approach works but scans every stored word on each query. What if we pre-computed all prefixes at insert time so that prefix lookups become instant?
Approach 2: HashMap for Words + HashSet for Prefixes
Intuition
Here is a clever middle-ground idea: what if we pre-compute all prefixes at insert time? When we insert "apple", we also store "a", "ap", "app", "appl", and "apple" as known prefixes. Then startsWith becomes an O(1) lookup.
For search, we use a separate set that only stores complete words. This avoids scanning and gives us O(1) for all three operations, at the cost of extra memory.
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 store duplicate prefix strings. What if we used a tree structure where shared prefixes are stored only once?
Approach 3: Trie (Prefix Tree)
Intuition
This is the approach the problem is specifically 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.
Here is the key insight: 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).
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 just checks if the path exists (no end-of-word check needed).
Since each node has at most 26 children (one per lowercase letter), we can use an array of size 26 for O(1) child access.
The Trie exploits the structure of the problem beautifully. Words that share a prefix share a path in the tree, so we never store redundant information. The 26-child array at each node gives us O(1) access to any child, making traversal as fast as possible.
The difference between search and startsWith comes down to a single boolean check. Both traverse the same path. search additionally verifies that the path ends at a complete word (isEnd == true), while startsWith is satisfied as long as the path exists. This is why a Trie is sometimes called a "prefix tree" -- prefix lookups are its native operation.
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.