# Implement Trie (Prefix Tree) LeetCode Solution

Here, We see Implement Trie (Prefix Tree) LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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

## Implement Trie (Prefix Tree) LeetCode SolutionC++

``````class TrieNode {
public:
TrieNode *child[26];
bool isWord;
TrieNode() {
isWord = false;
for (auto &a : child) a = nullptr;
}
};
class Trie {
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string s) {
TrieNode *p = root;
for (auto &a : s) {
int i = a - 'a';
if (!p->child[i]) p->child[i] = new TrieNode();
p = p->child[i];
}
p->isWord = true;
}
bool search(string key, bool prefix=false) {
TrieNode *p = root;
for (auto &a : key) {
int i = a - 'a';
if (!p->child[i]) return false;
p = p->child[i];
}
if (prefix==false) return p->isWord;
return true;
}
bool startsWith(string prefix) {
return search(prefix, true);
}
};```Code language: PHP (php)```

## Implement Trie (Prefix Tree) LeetCode SolutionJava

``````class Trie {
Node root;

public Trie() {
root = new Node();
}

public void insert(String word) {
root.insert(word, 0);
}

public boolean search(String word) {
return root.search(word, 0);
}

public boolean startsWith(String prefix) {
return root.startsWith(prefix, 0);
}

class Node {
Node[] nodes;
boolean isEnd;

Node() {
nodes = new Node[26];
}

private void insert(String word, int idx) {
if (idx >= word.length()) return;
int i = word.charAt(idx) - 'a';
if (nodes[i] == null) {
nodes[i] = new Node();
}

if (idx == word.length()-1) nodes[i].isEnd = true;
nodes[i].insert(word, idx+1);
}

private boolean search(String word, int idx) {
if (idx >= word.length()) return false;
Node node = nodes[word.charAt(idx) - 'a'];
if (node == null) return false;
if (idx == word.length() - 1 && node.isEnd) return true;

return node.search(word, idx+1);

}

private boolean startsWith(String prefix, int idx) {
if (idx >= prefix.length()) return false;
Node node = nodes[prefix.charAt(idx) - 'a'];
if (node == null) return false;
if (idx == prefix.length() - 1) return true;

return node.startsWith(prefix, idx+1);
}
}
}```Code language: JavaScript (javascript)```

## Implement Trie (Prefix Tree) SolutionJavaScript

``````var Trie = function() {
this.root = {};
};

Trie.prototype.insert = function(word) {
let node = this.root;
word.split('').forEach((char)=>{
if (!node[char]) node[char] = {};
node = node[char];
})
node.isEnd = true;
};

Trie.prototype.search = function(word) {
let node = this.searchNode(word);
return node!=null?node.isEnd==true:false;
};

Trie.prototype.startsWith = function(prefix) {
let node = this.searchNode(prefix);
return node != null;
};

Trie.prototype.searchNode = function(word) {
let node = this.root;
for (let char of word.split('')) {
if (node[char]) {
node = node[char]
} else {
return null;
}
}
return node;
}```Code language: JavaScript (javascript)```

## Implement Trie (Prefix Tree) SolutionPython

``````class Trie:
def __init__(self):
self.root={}

def insert(self, word) :
cur=self.root
for letter in word:
if letter not in cur:
cur[letter]={}
cur=cur[letter]
cur['*']=''

def search(self, word):
cur=self.root
for letter in word:
if letter not in cur:
return False
cur=cur[letter]
return '*' in cur

def startsWith(self, prefix):
cur=self.root
for letter in prefix:
if letter not in cur:
return False
cur=cur[letter]
return True``````
Scroll to Top