Data structures and algorithms
## Implement Trie (Prefix Tree)

###### Example 1:

###### Constraints:

##### Solution:

###### Time/Space Complexity:

###### Explanation:

comments powered by Disqus

**Implement Trie (Prefix Tree):**
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.

```
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
```

`1 <= word.length, prefix.length <= 2000`

`word`

and`prefix`

consist only of lowercase English letters.- At most
`3 * 10^4`

calls**in total**will be made to`insert`

,`search`

, and`startsWith`

.

Try this Problem on your own or check similar problems:

```
class Trie {
private class TrieNode{
TrieNode[] children;
boolean isWord = false;
public TrieNode(){
children = new TrieNode[26];
}
}
TrieNode root;
public Trie() {
root = new TrieNode();
}
private TrieNode searchPrefix(String prefix){
TrieNode iter = root;
for(int i = 0; i < prefix.length(); ++i){
char letter = prefix.charAt(i);
if(iter.children[letter - 'a'] == null){
return null;
}
iter = iter.children[letter - 'a'];
}
return iter;
}
public void insert(String word) {
TrieNode iter = root;
for(int i = 0; i < word.length(); ++i){
char letter = word.charAt(i);
if(iter.children[letter - 'a'] == null){
iter.children[letter - 'a'] = new TrieNode();
}
iter = iter.children[letter - 'a'];
}
iter.isWord = true;
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isWord;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
}
```

- Time Complexity:
*O(sum(w))*where`sum(w)`

sum of lengths of all inserted words - Space Complexity:
*O(sum(w))*

You can think of trie as a k-ary search tree where each node can have k children, in this case each `TrieNode`

can have `26 children`

(since we only deal with lowercase English letters), also note that each `TrieNode`

holds the information `isWord`

which indicates that current node is the end letter of the inserted word. At the `Trie`

constructor we define the root which will be the entry point for both read and writes to the trie. For inserting the word, we start with our root and check if it has child at index corresponding to the first letter in the word `letter - 'a'`

, if not we create it (with its set of children), then we move to that new node following the edge that matches the first letter. We follow the same pattern for all other letters of the word we’re inserting into the trie. The same goes for `search`

and `startsWith`

we utilize the `searchPrefix`

method which will traverse the trie and return the `TrieNode`

matching the last letter in the `prefix`

, note that for `startsWith`

it is enough to just check if the returned node is not `null`

, but for `search(word)`

we also have to check `node.isWord`

flag.

Don’t settle for anything less than the crown. Join our newsletter and become the King of Interviews! **Click here** to join now and get the latest updates.