A 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 :
- Autocomplete in mobile and web applications
- Spelling checker
- 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!