A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object.void insert(String word) Inserts the string word into the trie.boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
Example 1:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
Constraints:
1 <= word.length, prefix.length <= 2000word and prefix consist only of lowercase English letters.3 * 104 calls in total will be made to insert, search, and startsWith.Problem Overview: Design a Trie (Prefix Tree) that supports three operations: insert(word), search(word), and startsWith(prefix). Each operation must efficiently process strings by sharing common prefixes across stored words.
Approach 1: Native Trie with Fixed Children Array (O(L) time per operation)
This approach builds a classic Trie where each node stores an array of size 26 for lowercase English letters. During insert, iterate through the characters of the word and create nodes if they don't exist. For search and startsWith, traverse the tree following character indexes. The key insight is prefix sharing: multiple words reuse the same nodes until their paths diverge. Each operation runs in O(L) time where L is the word length, because you process one character at a time. Space complexity is O(N * L) in the worst case for storing all characters across inserted words. This implementation is extremely fast due to constant-time array access.
Approach 2: Trie Using Hash Maps (O(L) time per operation)
Instead of allocating a fixed array of 26 children, each node stores a dynamic map (hash table) from character to child node. While inserting a word, check the map for the next character and create a node only when necessary. search and startsWith follow the same traversal logic but rely on hash lookups. The time complexity remains O(L) per operation, but space becomes more efficient for sparse datasets because nodes only store existing edges. The tradeoff is slightly slower lookups due to hashing compared to array indexing. This approach combines concepts from hash tables and tries and is easier to generalize when the character set is large.
Both approaches exploit prefix compression: shared prefixes reduce redundant storage and allow quick prefix checks. This makes Tries particularly effective for autocomplete systems, dictionary lookups, and prefix-based search features.
Recommended for interviews: The fixed-array Trie is the implementation most interviewers expect. It demonstrates clear understanding of data structure design and delivers predictable O(L) operations with minimal overhead. The hash-map variant is useful when the character set is large or memory usage matters. Showing both approaches signals strong understanding of tradeoffs.
This approach involves creating a basic Trie data structure using a tree of nodes. Each node represents a character in a word. Starting from a root node, each character of the word is inserted sequentially, with branches representing the progression to subsequent characters. This forms a chain of nodes (linked in a tree-like manner) from the root to the nodes representing complete words. For searching, we traverse these nodes based on the characters of the input word or prefix to check for existence.
We first define a TrieNode structure with a children array to hold 26 letters and a boolean isEndOfWord to check if a node marks the end of a word. The createNode function initializes each node. TrieCreate initializes the trie by setting the root node.
The methods work by converting each character of the word or prefix into an index (0-25 for 'a'-'z'), navigating the children array of nodes for insertion or search operations. The insert function loops through each character, generating nodes along the path if needed, setting the isEndOfWord flag at the end. The search verifies both existence and termination of the string in the Trie, while startsWith logic only requires the prefix traversal.
Time Complexity: Insert, search, and startsWith operations are O(m), where m is the length of the word/prefix.
Space Complexity: O(26 * n * m) in the worst case, where n is the number of inserted words and m is the average length of the words. Each insertion can potentially add m nodes with 26 possible children each.
This approach relies on maps (or hashmaps) for storing children nodes dynamically. The advantage of using maps over arrays in this context arises from reduced space consumption when handling sparse trees since only existing characters are stored. Nodes manage their children using hash references, leading to more flexible branching.
This C++ implementation employs unordered_map in place of fixed-arrays to maintain child nodes in a Trie. Each TrieNode can dynamically allocate space only for characters that appear, leading to memory efficiency especially when nodes have very few immediate child nodes compared to the alphabet size. Insert, search, and startsWith operate similarly as before, now using map functionalities (find) to identify existing children and allocate if necessary.
C++
Python
JavaScript
Time Complexity: O(m) per operation where m is the word/prefix length.
Space Complexity: O(n * m), where n estimates the word count and m accounts for varying lengths since nodes only maintain necessary mappings.
We start from the root of the trie and insert the string. For the child node corresponding to the current character, there are two cases:
children array, then move along the pointer to the child node and continue searching for the next character.Repeat the above steps until the last character of the string is processed, then mark the current node as the end of the string.
We start from the root of the trie and search for the prefix. For the child node corresponding to the current character, there are two cases:
Repeat the above steps until a null pointer is returned or the last character of the prefix is searched.
If we search to the end of the prefix, it means the trie contains the prefix. Additionally, if the isEnd of the node corresponding to the end of the prefix is true, it means the trie contains the string.
The time complexity for inserting a string is O(m times |\Sigma|), and the time complexity for searching a prefix is O(m), where m is the length of the string and |\Sigma| is the size of the character set (26 in this problem). The space complexity is O(q times m times |\Sigma|), where q is the number of inserted strings.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Native Trie Implementation | Time Complexity: Insert, search, and startsWith operations are O(m), where m is the length of the word/prefix. |
| Comprehensive Trie using Maps | Time Complexity: O(m) per operation where m is the word/prefix length. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Native Trie with Fixed Array | O(L) per operation | O(N * L) | Standard interview solution when alphabet size is fixed (e.g., lowercase letters) |
| Trie Using Hash Maps | O(L) average | O(N * L) | Better when character set is large or the trie is sparse |
Implement Trie (Prefix Tree) - Leetcode 208 • NeetCode • 296,869 views views
Watch 9 more video solutions →Practice Implement Trie (Prefix Tree) with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor