Trie Data Structure — Prefix Tree Guide
In this tutorial, you'll learn about Trie Data Structure. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
A trie (pronounced "try"), also called a prefix tree, is a tree data structure that stores strings by sharing common prefixes. Each node represents a single character, and paths from root to leaf spell out stored words.
What You'll Learn
You will learn trie implementation (insert, search, prefix matching), autocomplete and spell-checking algorithms, memory optimization with compressed tries, and real-world applications.
Why It Matters
Tries enable O(k) string operations (where k is string length), regardless of how many strings are stored. They outperform hash tables for prefix-based searches and are essential for autocomplete, spell checkers, and IP routing.
Real-World Use
Doda Browser's URL autocomplete uses a trie. When you type "do" in the address bar, the trie finds all completions starting with "do" in O(k + m) time where k is prefix length and m is number of completions. A Hash Table would require scanning all entries.
Trie Structure
graph TD
R((root)) --> C[c]
R --> A[a]
R --> B[b]
C --> CA[a]
CA --> CAT[t*]
A --> AP[p]
AP --> APP[p]
APP --> APPL[l]
APPL --> APPLE[e*]
AP --> ARE[e*]
B --> BA[a]
BA --> BAT[t*]
style R fill:#4a90d9,stroke:#333,color:#fff
style CAT fill:#e67e22,stroke:#333,color:#fff
style APPLE fill:#e67e22,stroke:#333,color:#fff
style ARE fill:#e67e22,stroke:#333,color:#fff
style BAT fill:#e67e22,stroke:#333,color:#fff
Nodes marked with * indicate the end of a valid word. Common prefixes share nodes: "cat" and "catch" share "ca".
Trie Implementation
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self._traverse(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._traverse(prefix) is not None
def _traverse(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
def autocomplete(self, prefix):
node = self._traverse(prefix)
if not node:
return []
result = []
self._dfs(node, prefix, result)
return result
def _dfs(self, node, prefix, result):
if node.is_end:
result.append(prefix)
for ch, child in node.children.items():
self._dfs(child, prefix + ch, result)
trie = Trie()
words = ["cat", "car", "care", "caret", "card", "bat", "ball"]
for w in words:
trie.insert(w)
print("Search 'cat':", trie.search("cat"))
print("Search 'dog':", trie.search("dog"))
print("Starts with 'ca':", trie.starts_with("ca"))
print("Autocomplete 'ca':", trie.autocomplete("ca"))
print("Autocomplete 'car':", trie.autocomplete("car"))
Expected output:
Search 'cat': True
Search 'dog': False
Starts with 'ca': True
Autocomplete 'ca': ['cat', 'car', 'care', 'caret', 'card']
Autocomplete 'car': ['car', 'care', 'caret', 'card']
class TrieNode {
constructor() {
this.children = {};
this.isEnd = false;
}
}
class Trie {
constructor() { this.root = new TrieNode(); }
insert(word) {
let node = this.root;
for (let ch of word) {
if (!node.children[ch]) node.children[ch] = new TrieNode();
node = node.children[ch];
}
node.isEnd = true;
}
search(word) {
let node = this._traverse(word);
return node !== null && node.isEnd;
}
startsWith(prefix) {
return this._traverse(prefix) !== null;
}
_traverse(prefix) {
let node = this.root;
for (let ch of prefix) {
if (!node.children[ch]) return null;
node = node.children[ch];
}
return node;
}
autocomplete(prefix) {
let node = this._traverse(prefix);
if (!node) return [];
let result = [];
this._dfs(node, prefix, result);
return result;
}
_dfs(node, prefix, result) {
if (node.isEnd) result.push(prefix);
for (let [ch, child] of Object.entries(node.children)) {
this._dfs(child, prefix + ch, result);
}
}
}
let trie = new Trie();
["cat", "car", "care", "caret", "card", "bat", "ball"].forEach(w => trie.insert(w));
console.log("Search 'cat':", trie.search("cat"));
console.log("Autocomplete 'ca':", trie.autocomplete("ca"));
Expected output:
Search 'cat': true
Autocomplete 'ca': [ 'cat', 'car', 'care', 'caret', 'card' ]
Delete Operation
Deleting a word from a trie requires care to avoid removing nodes shared by other words:
def delete(self, word):
def _delete(node, word, depth):
if depth == len(word):
if not node.is_end:
return False
node.is_end = False
return len(node.children) == 0
ch = word[depth]
if ch not in node.children:
return False
should_delete_child = _delete(node.children[ch], word, depth + 1)
if should_delete_child:
del node.children[ch]
return len(node.children) == 0 and not node.is_end
return False
_delete(self.root, word, 0)
Memory-Efficient Tries
Standard tries use significant memory due to per-node hash maps. Optimizations include:
- Array-based children: Use a size-26 array for lowercase English letters
- Compressed (Radix) trie: Merge single-child nodes into one
- Ternary search tree: Combine trie and BST properties
class ArrayTrieNode:
def __init__(self):
self.children = [None] * 26
self.is_end = False
class ArrayTrie:
def __init__(self):
self.root = ArrayTrieNode()
def _index(self, ch):
return ord(ch) - ord('a')
def insert(self, word):
node = self.root
for ch in word:
idx = self._index(ch)
if not node.children[idx]:
node.children[idx] = ArrayTrieNode()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self.root
for ch in word:
idx = self._index(ch)
if not node.children[idx]:
return False
node = node.children[idx]
return node.is_end
Common Pitfalls
1. Not Marking Word Endings
Inserting "cat" and "catalog" — searching for "cat" returns false if is_end isn't set. Always mark the terminal node.
2. Memory Explosion
Each node creates a dictionary. For large alphabets (Unicode), this is expensive. Use array-based nodes for fixed alphabets.
3. Case Sensitivity
"Cat" and "cat" are different. Normalize input to lowercase unless case sensitivity is intentional.
4. Deleting Shared Nodes
When deleting "car", don't remove the "c" node — it's shared with "cat". Deletion should only remove unshared branches.
5. Not Handling Empty Strings
An empty string prefix matches everything. Ensure starts_with("") returns True, and search("") matches only if the root is marked as an end.
Practice Questions
1. Find all words in a trie that match a pattern with wildcards (e.g., "c.t").
def search_pattern(node, pattern, idx, prefix):
if idx == len(pattern):
return [prefix] if node.is_end else []
result = []
if pattern[idx] == '.':
for ch, child in node.children.items():
result.extend(search_pattern(child, pattern, idx + 1, prefix + ch))
elif pattern[idx] in node.children:
result.extend(search_pattern(node.children[pattern[idx]], pattern, idx + 1, prefix + pattern[idx]))
return result
2. Find the longest common prefix among all words in a trie.
3. Count the number of words that start with a given prefix.
4. Challenge: Implement a spell checker that suggests corrections for misspelled words using edit distance (Levenshtein) within a trie.
5. Real-world task: Doda Browser's ad blocker uses a trie to match URL patterns against known ad domains. Write a function that loads a list of blocked domain patterns (like "*.ads.example.com") into a trie and checks URLs against it.
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro