🎯 Objective: Learn what a Trie data structure is and how to implement it in Java.
📝 Table of Contents
1️⃣ What is Trie?
Trie, pronounced as “try,” is a tree-like data structure used for efficient retrieval of information, generally in the form of words. It’s essentially a character-based tree where each node represents a single character of a word.
2️⃣ Why use Trie?
- Autocomplete suggestions
- Spell checker
- IP routing (Longest prefix matching)
- Lexicographic sorting
3️⃣ How Trie Works
Trie is built on the principles of a tree structure. Each node has multiple child nodes, one for each character. Leaf nodes typically mark the end of a word.
For example, for the words “apple,” “bat,” and “batman,” the Trie would look like:
# <------ root node
/ \
a b
| |
p a
| |
p t
| / \
l m t
| | |
e a m
| |
n a
|
n
4️⃣ Java Implementation
Let’s implement Trie using Java.
public class TrieNode {
private TrieNode[] children;
private boolean isEndOfWord;
public TrieNode() {
this.children = new TrieNode[26]; // Assuming only lowercase English letters
this.isEndOfWord = false;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Insert 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.isEndOfWord = true;
}
// Search for a word in the Trie
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.children[c - 'a'];
if (node == null) return false;
}
return node.isEndOfWord;
}
// Main method for testing
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("apple");
trie.insert("bat");
trie.insert("batman");
System.out.println(trie.search("apple")); // Output: true
System.out.println(trie.search("bat")); // Output: true
System.out.println(trie.search("banana")); // Output: false
}
}5️⃣ Summary
You’ve now learned what a Trie is, why it’s useful, and how to implement it in Java. I hope this guide helps you understand this fascinating data structure better!