Trie — String-Specific Data Structure
After completing this topic, you will be able to:
Explain the structure and working principles of a Trie, and implement insertion, search, and prefix search to create features like autocomplete.
Problem: Searching Among Thousands of Words
We have a dictionary with 100,000 words. We want to display suggestions like "program," "project," and "process" when the user types "pro."
Comparing one by one in a list? 100,000 × string comparison = slow. A hash table can only find exact keys, making it unsuitable for prefix searches.
The Trie (derived from "retrieval") is a data structure created to solve this problem.
Trie Structure
A Trie is one node per character. Words that share the same prefix share the same path:
root
├── a
│ ├── p
│ │ └── p ★ ("app")
│ │ └── l
│ │ └── e ★ ("apple")
│ └── c
│ └── e ★ ("ace")
└── b
├── a
│ └── t ★ ("bat")
└── e ★ ("be")★ indicates "the word ends here." "app" and "apple" share the same path, with "app" ending once and "apple" ending once.
Implementation: Node
class TrieNode: def __init__(self): self.children = {} self.is_end = FalseEach node has a dictionary of child nodes (children) and a word-end indicator (is_end).
Insertion
class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.is_end = Truetrie = Trie()for word in ["app", "apple", "ace", "bat", "be"]: trie.insert(word)Traverse the characters one by one, creating a new node if the path doesn't exist. Mark the last character with is_end = True.
Search
def search(self, word): node = self.root for char in word: if char not in node.children: return False node = node.children[char] return node.is_endprint(trie.search("app")) # Trueprint(trie.search("ap")) # False — no word ends with "ap"print(trie.search("apple")) # Trueprint(trie.search("bat")) # Trueprint(trie.search("bad")) # FalseIf the path doesn't exist, return False. If it reaches the end but is_end is not True, return False (it's just a prefix, not a complete word).
Prefix Search — Key to Autocomplete
def starts_with(self, prefix): node = self.root for char in prefix: if char not in node.children: return [] node = node.children[char] results = [] self._collect(node, prefix, results) return results
def _collect(self, node, prefix, results): if node.is_end: results.append(prefix) for char, child in node.children.items(): self._collect(child, prefix + char, results)print(trie.starts_with("a")) # ["app", "apple", "ace"]print(trie.starts_with("ap")) # ["app", "apple"]print(trie.starts_with("b")) # ["bat", "be"]print(trie.starts_with("z")) # []Traverse to the prefix, then collect all complete words below it. This is the principle behind search engine autocomplete and IDE code completion.
Time Complexity
| Operation | Time Complexity | Comparison (Hash Table) |
|---|---|---|
| Insertion | O(m) | O(m) |
| Exact Search | O(m) | O(m) |
| Prefix Search | O(m + k) | ❌ Not possible |
m = string length, k = number of results below the prefix.
The exact search performance is similar to a hash table, but only a Trie can perform prefix-based searches. A hash table needs to perform a full scan to find all keys starting with "pro."
Memory Trade-off
The downside of a Trie is its memory usage. Each node has a dictionary, and even with just lowercase English letters, it requires up to 26 child pointers.
Improved variations:
- Compressed Trie (Radix Tree): Compresses paths by merging nodes with only one child.
- Ternary Search Tree: Combines with a binary search tree to save memory.
In practice, libraries usually handle the optimization, so understanding the principles is sufficient.
Practical Applications
| Use Case | Description |
|---|---|
| Search Autocomplete | Google, IDE code completion |
| Spell Check | Checking if an input word exists in a dictionary |
| IP Routing | Network prefix matching (longest prefix match) |
| T9 Keypad | Converting numbers to letters and searching for candidate words |
Deletion Implementation
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 char = word[depth] if char not in node.children: return False should_remove = _delete(node.children[char], word, depth + 1) if should_remove: del node.children[char] return not node.is_end and len(node.children) == 0 return False _delete(self.root, word, 0)When deleting a word, only the unique nodes of that word (not shared with other words) are removed. Deleting "apple" leaves the nodes required for "app" intact.
Counting Trie
If you record the number of insertions, you get a word frequency dictionary:
class CountTrie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.is_end = True node.count = getattr(node, 'count', 0) + 1 def count(self, word): node = self.root for char in word: if char not in node.children: return 0 node = node.children[char] return getattr(node, 'count', 0) if node.is_end else 0Used for aggregating search term frequencies and determining autocomplete ranking.
Simple Trie Alternative in Python
You don't need to implement a Trie directly; you can achieve a similar effect with nested dictionaries:
from collections import defaultdict
def make_trie(words): trie = lambda: defaultdict(trie) root = trie() for word in words: node = root for c in word: node = node[c] node['$'] = True return root
t = make_trie(["app", "apple", "bat"])print("app" in str(t)) # TrueHowever, if you need prefix-based functionality like starts_with, a class-based implementation is cleaner. In coding tests, a class implementation is standard.
A Trie is suitable for any scenario that involves dealing with a set of strings that share prefixes.