304 North Cardinal St.
Dorchester Center, MA 02124

# Implement Trie (Prefix Tree) LeetCode Solution

## Problem – Implement Trie (Prefix Tree)

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 <= 2000`
• `word` and `prefix` consist only of lowercase English letters.
• At most `3 * 104` calls in total will be made to `insert``search`, and `startsWith`.

### Implement Trie (Prefix Tree) LeetCode Solution in Python

``````class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.word=False
self.children={}

class Trie:

def __init__(self):
self.root = TrieNode()

# @param {string} word
# @return {void}
# Inserts a word into the trie.
def insert(self, word):
node=self.root
for i in word:
if i not in node.children:
node.children[i]=TrieNode()
node=node.children[i]
node.word=True

# @param {string} word
# @return {boolean}
# Returns if the word is in the trie.
def search(self, word):
node=self.root
for i in word:
if i not in node.children:
return False
node=node.children[i]
return node.word

# @param {string} prefix
# @return {boolean}
# Returns if there is any word in the trie
# that starts with the given prefix.
def startsWith(self, prefix):
node=self.root
for i in prefix:
if i not in node.children:
return False
node=node.children[i]
return True

# Your Trie object will be instantiated and called as such:
# trie = Trie()
# trie.insert("somestring")
# trie.search("key")
``````

### Implement Trie (Prefix Tree) LeetCode Solution in Java

``````class TrieNode {
public char val;
public boolean isWord;
public TrieNode[] children = new TrieNode;
public TrieNode() {}
TrieNode(char c){
TrieNode node = new TrieNode();
node.val = c;
}
}

public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
root.val = ' ';
}

public void insert(String word) {
TrieNode ws = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(ws.children[c - 'a'] == null){
ws.children[c - 'a'] = new TrieNode(c);
}
ws = ws.children[c - 'a'];
}
ws.isWord = true;
}

public boolean search(String word) {
TrieNode ws = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(ws.children[c - 'a'] == null) return false;
ws = ws.children[c - 'a'];
}
return ws.isWord;
}

public boolean startsWith(String prefix) {
TrieNode ws = root;
for(int i = 0; i < prefix.length(); i++){
char c = prefix.charAt(i);
if(ws.children[c - 'a'] == null) return false;
ws = ws.children[c - 'a'];
}
return true;
}
}
``````

### Implement Trie (Prefix Tree) LeetCode Solution in C++

``````class TrieNode
{
public:
TrieNode *next;
bool is_word;

// Initialize your data structure here.
TrieNode(bool b = false)
{
memset(next, 0, sizeof(next));
is_word = b;
}
};

class Trie
{
TrieNode *root;
public:
Trie()
{
root = new TrieNode();
}

// Inserts a word into the trie.
void insert(string s)
{
TrieNode *p = root;
for(int i = 0; i < s.size(); ++ i)
{
if(p -> next[s[i] - 'a'] == NULL)
p -> next[s[i] - 'a'] = new TrieNode();
p = p -> next[s[i] - 'a'];
}
p -> is_word = true;
}

// Returns if the word is in the trie.
bool search(string key)
{
TrieNode *p = find(key);
return p != NULL && p -> is_word;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix)
{
return find(prefix) != NULL;
}

private:
TrieNode* find(string key)
{
TrieNode *p = root;
for(int i = 0; i < key.size() && p != NULL; ++ i)
p = p -> next[key[i] - 'a'];
return p;
}
};
``````
##### Implement Trie (Prefix Tree) LeetCode Solution Review:

In our experience, we suggest you solve this Implement Trie (Prefix Tree) LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Implement Trie (Prefix Tree) LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Implement Trie (Prefix Tree) LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions