Introduction
Tries, also known as prefix trees, are an extremely powerful data structure when it comes to handling string-related problems efficiently. If you're dealing with autocomplete systems, dictionary validations, or prefix-based searches, Tries might just be your best tool.
🧠 What is a Trie?
A Trie (pronounced try) is a tree-like data structure used to store a dynamic set or associative array where the keys are usually strings.
Each node in the trie represents a character of a string, and the path from the root to a node represents a prefix of the string. Nodes can also contain a flag to indicate whether a word ends at that node.
🧰 Core Operations
1. Insert
Description: Add a word character by character
Time Complexity: O(L)
2. Search
Description: Check if a word exists in the trie
Time Complexity: O(L)
3. Prefix Search
Description: Check if a prefix exists in the trie
Time Complexity: O(L)
4. Delete (Optional)
Description: Remove a word from the trie
Time Complexity: O(L)
L = Length of the word
🔍 How Tries Work – An Example
Let's insert the words: "cat", "cap", "can"
Root
├── c
├── a
├── t (end)
├── p (end)
├── n (end)
This structure allows us to:
Quickly check if a word exists
Suggest all words with the prefix "ca"
Save space by sharing common prefixes
🧱 Memory Layout
Each node of a Trie typically stores:
A map/array of child nodes (one for each character, often 26 for lowercase English)
A boolean flag to indicate end-of-word
Java Implementation Example:
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord = false;
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Insert a word
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null)
node.children[idx] = new TrieNode();
node = node.children[idx];
}
node.isEndOfWord = true;
}
// Search a word
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null)
return false;
node = node.children[idx];
}
return node.isEndOfWord;
}
// Check prefix
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null)
return false;
node = node.children[idx];
}
return true;
}
}
🎯 Real-World Applications
Search engines (autocomplete)
Spell checkers
IP routing (binary tries)
Word games like Boggle and Scrabble
Dictionary implementation
📘 LeetCode Practice Problems
Implement Trie (Prefix Tree) – Medium – LeetCode#208
Replace Words – Medium – LeetCode#648
Add and Search Word – Medium – LeetCode#211
Longest Word in Dictionary – Medium – LeetCode#720
Word Search II – Hard – LeetCode#212
🎯 Tips for Interview Preparation
Be comfortable building TrieNode classes with arrays and HashMaps.
Practice writing insert and search operations quickly and correctly.
Focus on common variations:
Word search using DFS + Trie
Wildcard searches (e.g., ".", "*")
Prefix and suffix matching
Optimize memory by storing only necessary characters or using a compressed Trie (Radix Tree) if applicable.
🔚 Wrapping Up
Tries offer a beautiful combination of speed and structure for problems involving strings and prefixes. They’re essential in fields like search engines, linguistics, and autocomplete systems. Mastering them will not only give you a powerful new tool but will also sharpen your understanding of how data structures can be customized for specialized problems.
Happy coding! 🚀
Nitin
Hashnode | Substack | LinkedIn | GIT | Youtube | Instagram
