# 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
// initializes 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 node = root;
int index = word.charAt(0) - 'a';

TrieNode[] nodes = node.getNodes();

for (char ch : word.toCharArray()) {

index = ch - 'a';

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

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

node.setEnd(true);
}

public TrieNode searchPrefix(String word) {

TrieNode node = root;
TrieNode[] nodes = node.getNodes();

for (char ch : word.toCharArray()) {

int index = ch - 'a';

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

return node;
}

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

// Returns true if there is any word in the Trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode node = searchPrefix(prefix);
return node != 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"));
}


Time Complexity
Insert: O(n), Search: O(n), n = length of the word

LeetCode problem

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

Happy programming!