# Trie – LeetCode Solution [Medium]

Trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

###### Applications

There are various applications of this special data structure such as :

1. Autocomplete in mobile and web applications
2. Spelling checker
3. Solving word games

and many more.

###### Implementation

Trie is an efficient information reTrieval data structure and hence the name Trie. It is a special data structure used to store strings. It consists of nodes and edges like a tree. Each node consists of 26 children (including null and non-null values) and each node is connected to its children and parent node. These 26 children are nothing but pointers for each of the 26 letters of the English alphabet. A variable isEnd is used to mark the end of a string present in Trie. This means, combining all the alphabets from root to present character having isEnd = true makes a word, present in Trie.

Strings are stored in a top to bottom manner on the basis of their prefix in a trie. For instance:

This is an example Trie structure for strings:

["bye", "hear", "here", "hi", "hit"]
###### Implementing Class for each Trie node
class TrieNode {

//Children nodes
private TrieNode[] nodes;

//MAX_SIZE = Number of alphabets
private final int MAX_SIZE = 26;

//To check if it's the last node of a string in trie
private boolean isEnd;

public TrieNode[] getNodes() {
return nodes;
}

public boolean isEnd() {
return isEnd;
}

public void setEnd(boolean isEnd) {
this.isEnd = isEnd;
}

// TrieNode constructor
// initialises TrieNode's every new object
public TrieNode() {
nodes = new TrieNode[MAX_SIZE];
isEnd = false;

for (int i=0; i<MAX_SIZE; i++) {
nodes[i] = null;
}

}

}

TrieNode class: Each object of this class is representing each node in Trie data structure
###### Implementing Class for Trie
class Trie {

TrieNode root;

// Initializing TrieNode object
public Trie() {
root = new TrieNode();
}

// Inserts a word into the trie.
public void insert(String word) {
TrieNode p = root;
int index = word.charAt(0) - 'a';

TrieNode[] nodes = p.getNodes();

for (int i=0; i<word.length(); i++) {
index = word.charAt(i) - 'a';

if (nodes[index] == null) {
nodes[index] = new TrieNode();
}

p = nodes[index];
nodes = p.getNodes();
}

p.setEnd(true);
}

public TrieNode searchPrefix(String word) {
TrieNode p = root;
TrieNode[] nodes = p.getNodes();

for (int i=0; i<word.length(); i++) {
int index = word.charAt(i) - 'a';

if (nodes != null && nodes[index] != null) {
p = nodes[index];
nodes = p.getNodes();
} else {
return null;
}
}

return p;
}

// Returns true if the word is in the trie.
public boolean search(String word) {
TrieNode p = searchPrefix(word);
return (p != null && p.isEnd());
}

// Returns true if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode p = searchPrefix(prefix);
return p != null;
}

};

###### Main function to run Trie:
    public static void main(String[] args) {
Trie obj = new Trie();
obj.insert("word");
System.out.println(obj.search("word"));
}


LeetCode problem

You could easily solve this LeetCode problem after understanding this Trie implementation:
Implement Trie (Prefix Tree)

Happy programming!