Implement Trie (Prefix Tree)
Med#0196Time: O(m) for all operations, where m is the length of the word/prefixSpace: O(N * 26 * M) where N is the number of words and M is average word length. Each node contains an array of size 26.17 companies
Prompt
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 stringwordinto the trie.boolean search(String word)Returnstrueif the stringwordis in the trie (i.e., was inserted before), andfalseotherwise.boolean startsWith(String prefix)Returnstrueif there is a previously inserted stringwordthat has the prefixprefix, andfalseotherwise.
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 <= 2000wordandprefixconsist only of lowercase English letters.- At most
3 * 104calls in total will be made toinsert,search, andstartsWith.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a simple array to store characters and implements a basic trie structure. Each node in the trie contains a boolean flag to mark the end of a word and an array of size 26 (for lowercase English letters) to store child nodes.
Algorithm
- Create a TrieNode class with an array of size 26 for children and a boolean flag
- For insert:
- Start from root
- For each character, create a new node if it doesn't exist
- Mark the last node as end of word
- For search:
- Traverse the trie following the characters
- Return true if last node exists and is marked as end of word
- For startsWith:
- Similar to search but only check if path exists
Walkthrough
In this approach, we create a TrieNode class that contains:
- A boolean flag
isEndOfWordto mark if the node represents the end of a word - An array of TrieNode references of size 26 for each possible lowercase letter
Here's the implementation:
class TrieNode { TrieNode[] children; boolean isEndOfWord; public TrieNode() { children = new TrieNode[26]; isEndOfWord = false; }} class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode current = root; for(char ch : word.toCharArray()) { int index = ch - 'a'; if(current.children[index] == null) { current.children[index] = new TrieNode(); } current = current.children[index]; } current.isEndOfWord = true; } public boolean search(String word) { TrieNode node = searchNode(word); return node != null && node.isEndOfWord; } public boolean startsWith(String prefix) { return searchNode(prefix) != null; } private TrieNode searchNode(String str) { TrieNode current = root; for(char ch : str.toCharArray()) { int index = ch - 'a'; if(current.children[index] == null) { return null; } current = current.children[index]; } return current; }}Complexity
Time
O(m) for all operations, where m is the length of the word/prefix
Space
O(N * 26 * M) where N is the number of words and M is average word length. Each node contains an array of size 26.
Trade-offs
Pros
Simple implementation with array indexing
Constant time lookup for children (array access)
Memory efficient for small alphabets
Cons
Fixed size array wastes space for sparse nodes
Not flexible for different character sets
Memory intensive for large character sets
This approach uses a HashMap instead of an array to store children in each node. This makes the implementation more flexible and potentially more space-efficient for sparse tries.
Algorithm
- Create a TrieNode class with a HashMap for children and a boolean flag
- For insert:
- Start from root
- For each character, create a new node if it doesn't exist in the HashMap
- Mark the last node as end of word
- For search:
- Traverse the trie using HashMap lookups
- Return true if last node exists and is marked as end of word
- For startsWith:
- Similar to search but only check if path exists
Walkthrough
In this approach, we use a HashMap to store child nodes, which allows for more flexible character sets and better space efficiency when the trie is sparse.
class TrieNode { Map<Character, TrieNode> children; boolean isEndOfWord; public TrieNode() { children = new HashMap<>(); isEndOfWord = false; }} class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode current = root; for(char ch : word.toCharArray()) { current.children.putIfAbsent(ch, new TrieNode()); current = current.children.get(ch); } current.isEndOfWord = true; } public boolean search(String word) { TrieNode node = searchNode(word); return node != null && node.isEndOfWord; } public boolean startsWith(String prefix) { return searchNode(prefix) != null; } private TrieNode searchNode(String str) { TrieNode current = root; for(char ch : str.toCharArray()) { if(!current.children.containsKey(ch)) { return null; } current = current.children.get(ch); } return current; }}Complexity
Time
O(m) for all operations, where m is the length of the word/prefix. HashMap operations are O(1) on average.
Space
O(N * M) where N is the number of words and M is average word length. Space is proportional to actual characters stored.
Trade-offs
Pros
More space-efficient for sparse tries
Flexible for different character sets
Dynamic memory allocation based on actual usage
Cons
Slightly slower than array-based approach due to HashMap operations
More memory overhead per node due to HashMap structure
Hash collisions could affect performance in extreme cases
Solutions
Solution
public class Trie { bool isEnd ; Trie [] children = new Trie [ 26 ]; public Trie () { } public void Insert ( string word ) { Trie node = this ; foreach ( var c in word ) { var idx = c - 'a' ; node . children [ idx ] ??= new Trie (); node = node . children [ idx ]; } node . isEnd = true ; } public bool Search ( string word ) { Trie node = SearchPrefix ( word ); return node != null && node . isEnd ; } public bool StartsWith ( string prefix ) { Trie node = SearchPrefix ( prefix ); return node != null ; } private Trie SearchPrefix ( string s ) { Trie node = this ; foreach ( var c in s ) { var idx = c - 'a' ; if ( node . children [ idx ] == null ) { return null ; } node = node . children [ idx ]; } return node ; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.Insert(word); * bool param_2 = obj.Search(word); * bool param_3 = obj.StartsWith(prefix); */public class Implement_Trie_Prefix_Tree { public static void main ( String [] args ) { Implement_Trie_Prefix_Tree out = new Implement_Trie_Prefix_Tree (); Trie trie = out . new Trie (); trie . insert ( "abc" ); trie . insert ( "ab" ); System . out . println ( trie . search ( "ab" )); trie . insert ( "ab" ); System . out . println ( trie . search ( "ab" )); System . out . println ( trie . startsWith ( "a" )); } class TrieNode { // R children to node children private TrieNode [] children ; private final int R = 26 ; private boolean isEnd ; public TrieNode () { children = new TrieNode [ R ]; } public boolean containsKey ( char ch ) { return children [ ch - 'a' ] != null ; } public TrieNode get ( char ch ) { return children [ ch - 'a' ]; } public void put ( char ch , TrieNode node ) { children [ ch - 'a' ] = node ; } public void setEnd () { isEnd = true ; } public boolean isEnd () { return isEnd ; } } class Trie { private TrieNode root ; public Trie () { root = new TrieNode (); } // Inserts a word into the trie. public void insert ( String word ) { TrieNode node = root ; // @note:@memorize: iteration is better than recursion during trie building for ( int i = 0 ; i < word . length (); i ++) { char currentChar = word . charAt ( i ); if (! node . containsKey ( currentChar )) { node . put ( currentChar , new TrieNode ()); } node = node . get ( currentChar ); } node . setEnd (); } // search a prefix or whole key in trie and // returns the node where search ends private TrieNode searchPrefix ( String word ) { TrieNode node = root ; for ( int i = 0 ; i < word . length (); i ++) { char curLetter = word . charAt ( i ); if ( node . containsKey ( curLetter )) { node = node . get ( curLetter ); } else { return null ; } } return node ; } // Returns if the word is in the trie. public boolean search ( String word ) { TrieNode node = searchPrefix ( word ); return node != null && node . isEnd (); } // Returns if there is any word in the trie // that starts with the given prefix. public boolean startsWith ( String prefix ) { TrieNode node = searchPrefix ( prefix ); return node != null ; } } // Your Trie object will be instantiated and called as such: // Trie trie = new Trie(); // trie.insert("somestring"); // trie.search("key"); } ////// class Trie { private Trie [] children ; private boolean isEnd ; public Trie () { children = new Trie [ 26 ]; } public void insert ( String word ) { Trie node = this ; for ( char c : word . toCharArray ()) { int idx = c - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; } node . isEnd = true ; } public boolean search ( String word ) { Trie node = searchPrefix ( word ); return node != null && node . isEnd ; } public boolean startsWith ( String prefix ) { Trie node = searchPrefix ( prefix ); return node != null ; } private Trie searchPrefix ( String s ) { Trie node = this ; for ( char c : s . toCharArray ()) { int idx = c - 'a' ; if ( node . children [ idx ] == null ) { return null ; } node = node . children [ idx ]; } return node ; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); *//** * Initialize your data structure here. */ var Trie = function () { this . children = {}; }; /** * Inserts a word into the trie. * @param {string} word * @return {void} */ Trie . prototype . insert = function ( word ) { let node = this . children ; for ( let char of word ) { if ( ! node [ char ]) { node [ char ] = {}; } node = node [ char ]; } node . isEnd = true ; }; /** * Returns if the word is in the trie. * @param {string} word * @return {boolean} */ Trie . prototype . search = function ( word ) { let node = this . searchPrefix ( word ); return node != undefined && node . isEnd != undefined ; }; Trie . prototype . searchPrefix = function ( prefix ) { let node = this . children ; for ( let char of prefix ) { if ( ! node [ char ]) return false ; node = node [ char ]; } return node ; }; /** * Returns if there is any word in the trie that starts with the given prefix. * @param {string} prefix * @return {boolean} */ Trie . prototype . startsWith = function ( prefix ) { return this . searchPrefix ( prefix ); }; /** * Your Trie object will be instantiated and called as such: * var obj = new Trie() * obj.insert(word) * var param_2 = obj.search(word) * var param_3 = obj.startsWith(prefix) */import collections class TrieNode : def __init__ ( self ): ''' Usually, a Python dictionary throws a KeyError if you try to get an item with a key that is not currently in the dictionary. The defaultdict in contrast will simply create any items that you try to access https://stackoverflow.com/questions/5900578/how-does-collections-defaultdict-work ''' self . child = collections . defaultdict ( TrieNode ) self . is_word = False class Trie : def __init__ ( self ): self . root = TrieNode () def insert ( self , word : str ) -> None : cur = self . root for letter in word : cur = cur . child [ letter ] cur . is_word = True def search ( self , word : str ) -> bool : cur = self . root for letter in word : # cur = cur.child[letter] ==> will not work, it will creat a default node for this letter cur = cur . child . get ( letter ) if not cur : return False return cur . is_word def startsWith ( self , prefix : str ) -> bool : cur = self . root for letter in prefix : # cur = cur.child[letter] ==> will not work, it will creat a default node for this letter cur = cur . child . get ( letter ) if not cur : return False return True # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix) ############ class Trie : def __init__ ( self ): self . children = [ None ] * 26 self . is_end = False def insert ( self , word : str ) -> None : node = self for c in word : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . is_end = True def search ( self , word : str ) -> bool : node = self . _search_prefix ( word ) return node is not None and node . is_end def startsWith ( self , prefix : str ) -> bool : node = self . _search_prefix ( prefix ) return node is not None def _search_prefix ( self , prefix : str ): node = self for c in prefix : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : return None node = node . children [ idx ] return node # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix) # below is using reduce() class Trie ( object ): def __init__ ( self ): T = lambda : collections . defaultdict ( T ) self . root = T () def insert ( self , word ): reduce ( dict . __getitem__ , word , self . root )[ '#' ] = True def search ( self , word ): return '#' in reduce ( lambda cur , c : cur . get ( c , {}), word , self . root ) def startsWith ( self , prefix ): return bool ( reduce ( lambda cur , c : cur . get ( c , {}), prefix , self . root ))// OJ: https://leetcode.com/problems/implement-trie-prefix-tree/ // Time: O(W) for insert/search/startsWith // Space: O(1) extra space for all struct TrieNode { TrieNode * next [ 26 ] = {}; bool word = false ; }; class Trie { TrieNode root ; TrieNode * find ( string & word ) { auto node = & root ; for ( char c : word ) { if ( ! node -> next [ c - 'a' ]) return NULL ; node = node -> next [ c - 'a' ]; } return node ; } public: void insert ( string word ) { auto node = & root ; for ( char c : word ) { if ( ! node -> next [ c - 'a' ]) node -> next [ c - 'a' ] = new TrieNode (); node = node -> next [ c - 'a' ]; } node -> word = true ; } bool search ( string word ) { auto node = find ( word ); return node && node -> word ; } bool startsWith ( string prefix ) { return find ( prefix ); } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.