# Solution For Implement Trie Prefix Tree

Problem Description:

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Example:

Trie trie = new Trie();

trie.insert(“apple”);

trie.search(“apple”); // returns true

trie.search(“app”); // returns false

trie.startsWith(“app”); // returns true

trie.insert(“app”);

trie.search(“app”); // returns true

Solution:

A Trie prefix tree is a tree data structure which is used to store the strings. Each node in the Trie represents a character of the string and stores the boolean value to indicate whether it is the end of a word. The Trie tree is used to find all the possible words by traversing all the nodes of the tree. Insertion in the Trie tree is performed by iterating each character of the string and checking if the character is already present in the Trie tree. If it is present, then move to the corresponding node of that character, otherwise create a new node and connect it with the Trie tree.

Algorithm:

The basic steps of the algorithm to create a Trie tree are:

Create a Trie class that contains an array of TrieNode.

Create a TrieNode class that contains an array of TrieNode and a boolean flag to track whether it is the end of the word.

Add methods to the Trie class to insert, search, and startWith.

To insert the string in the Trie tree, move through each character of the string. If the character is not present in the Trie tree, then create a new TrieNode with the character as the value of the TrieNode. Continue until the entire string is traversed.

At the end of the last character, set the boolean flag of the TrieNode to true.

To search for a string in the Trie tree, iterate each character of the string and check if the corresponding TrieNode of that character is present. If it is present, then move to the corresponding node of that character.

After iterating through all the characters of the string, return true if the final TrieNode boolean flag is true, otherwise false.

To startWith a string in the Trie tree, iterate through each character of the string and check if the corresponding TrieNode of that character is present. If it is present, then move to the corresponding node of that character.

After iterating through all the characters of the string, return true.

Code in Python:

class TrieNode:
def init(self):
self.children = [None]*26
self.isEndOfWord = False

class Trie:
def init(self):
self.root = TrieNode()

``````def insert(self, word: str) -> None:
node = self.root
for c in word:
index = ord(c)-ord('a')
if not node.children[index]:
node.children[index] = TrieNode()
node = node.children[index]
node.isEndOfWord = True

def search(self, word: str) -> bool:
node = self.root
for c in word:
index = ord(c)-ord('a')
if not node.children[index]:
return False
node = node.children[index]
return node.isEndOfWord

def startsWith(self, prefix: str) -> bool:
node = self.root
for c in prefix:
index = ord(c)-ord('a')
if not node.children[index]:
return False
node = node.children[index]
return True
``````

# main function

if name == ‘main‘:
trie = Trie()
trie.insert(“apple”)
print(trie.search(“apple”)) # returns true
print(trie.search(“app”)) # returns false
print(trie.startsWith(“app”)) # returns true
trie.insert(“app”)
print(trie.search(“app”)) # returns true

The above code creates a Trie tree and adds the string ‘apple’. The search operation is performed to check if the string ‘apple’ is present in the Trie tree or not. The startsWith operation is performed to check if the character ‘a’ is starting with in the Trie tree or not. The Trie tree is then updated by adding the string ‘app’. Again the search operation is performed to check if the string ‘app’ is present in the Trie tree or not.

## Step by Step Implementation For Implement Trie Prefix Tree

```class TrieNode {
// Initialize your data structure here.
char c;
HashMap children = new HashMap();
boolean isLeaf;

public TrieNode() {}

public TrieNode(char c){
this.c = c;
}
}

public class Trie {
private TrieNode root;

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

// Inserts a word into the trie.
public void insert(String word) {
HashMap children = root.children;

for(int i=0; i children = root.children;
TrieNode t = null;
for(int i=0; i

class TrieNode:

def __init__(self):
self.children = {}
self.is_end_of_word = False

def insert(self, key):
if not key:
return

node = self
for char in key:
if char not in node.children:
node.children[char] = TrieNode()

node = node.children[char]

node.is_end_of_word = True

def search(self, key):
if not key:
return False

node = self
for char in key:
if char not in node.children:
return False

node = node.children[char]

return node.is_end_of_word

def starts_with(self, prefix):
if not prefix:
return False

node = self
for char in prefix:
if char not in node.children:
return False

node = node.children[char]

return Truevar Trie = function() {
this.root = new TrieNode();
};

/**
* Inserts a word into the trie.
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
var node = this.root;

for (var i = 0; i < word.length; i++) {
var char = word[i];

if (!node.children[char]) {
node.children[char] = new TrieNode();
}

node = node.children[char];
}

node.isWord = true;
};

/**
* Returns if the word is in the trie.
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
var node = this.root;

for (var i = 0; i < word.length; i++) {
var char = word[i];

if (!node.children[char]) {
return false;
}

node = node.children[char];
}

return node.isWord;
};

/**
* 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) {
var node = this.root;

for (var i = 0; i < prefix.length; i++) {
var char = prefix[i];

if (!node.children[char]) {
return false;
}

node = node.children[char];
}

return true;
};

/**
* 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)
*/class TrieNode {
public:
// Initialize your data structure here.
TrieNode() {
isWord = false;
for (int i = 0; i < 26; i++)
children[i] = NULL;
}
bool isWord;
TrieNode* children[26];
};

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

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

// Returns if the word is in the trie.
bool search(string key) {
TrieNode* cur = root;
for (int i = 0; i < key.size(); i++) {
if (cur->children[key[i] - 'a'] == NULL) {
return false;
}
cur = cur->children[key[i] - 'a'];
}
return cur->isWord;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode* cur = root;
for (int i = 0; i < prefix.size(); i++) {
if (cur->children[prefix[i] - 'a'] == NULL) {
return false;
}
cur = cur->children[prefix[i] - 'a'];
}
return true;
}

private:
TrieNode* root;
};

// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");using System;
using System.Collections.Generic;

public class TrieNode {
public TrieNode[] children = new TrieNode[26];
public bool isWord;

public TrieNode() {}
}

public class Trie {
private TrieNode root;

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

// Inserts a word into the trie.
public void Insert(string word) {
TrieNode node = root;
for (char c : word.ToCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.isWord = true;
}

// Returns if the word is in the trie.
public bool Search(string word) {
TrieNode node = root;
for (char c : word.ToCharArray()) {
if (node.children[c - 'a'] == null) {
return false;
}
node = node.children[c - 'a'];
}
return node.isWord;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
public bool StartsWith(string prefix) {
TrieNode node = root;
for (char c : prefix.ToCharArray()) {
if (node.children[c - 'a'] == null) {
return false;
}
node = node.children[c - 'a'];
}
return true;
}
}

// 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);```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]