Introduction
A trie (pronounced 'try', short for retrieval tree) is a tree structure specialized for storing and searching strings. Instead of comparing whole keys like a hash table or BST, a trie stores one character per edge, so strings that share a prefix share the same path from the root. This makes operations like insert, search, and prefix lookup run in O(m) time, where m is the length of the key, completely independent of how many keys are stored. Tries power autocomplete systems, spell checkers, IP routing tables, and dictionary implementations.
Cricket analogy: A trie is like a coaching manual indexed letter by letter for player surnames — 'Sh-a-r-m-a' and 'Sh-a-s-t-r-i' share the 'Sh-a' path — so looking up any name takes time proportional only to its length, m, no matter how many players are in the database.
Structure/Syntax
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end_of_word = 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_of_word = TrueExplanation
Each TrieNode holds a dictionary mapping a character to the child node reached by that character, plus a boolean flag marking whether a complete word ends at that node. Inserting a word walks the tree character by character, creating new nodes only when a path does not already exist, then marks the final node as a word end. Because branches are shared among words with common prefixes (for example 'car', 'card', and 'care' all reuse the 'c'-'a'-'r' path), a trie can be far more space-efficient than storing each string independently when the vocabulary has heavy prefix overlap.
Cricket analogy: Each node in the surname trie holds a map from the next letter to a child node plus a flag marking a complete surname; inserting 'Sharma' creates new letter-nodes only where the path is missing, and since 'Sharma' and 'Sharad' share 'Sh-a-r', storing both is cheaper than two separate full names.
Example
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end_of_word = True
def search(self, word):
node = self._find_node(word)
return node is not None and node.is_end_of_word
def starts_with(self, prefix):
return self._find_node(prefix) is not None
def _find_node(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
trie = Trie()
for word in ["car", "card", "care", "cat", "dog"]:
trie.insert(word)
print(trie.search("car")) # True
print(trie.search("ca")) # False (not a complete word)
print(trie.starts_with("ca")) # True
print(trie.starts_with("do")) # True
print(trie.search("dogs")) # FalseComplexity
Insert and search both run in O(m) time and O(1) extra space beyond the trie itself, where m is the length of the key being processed — the number of stored words n never enters the time cost. This is strictly better than a balanced BST's O(m log n) comparison cost for string keys. The tradeoff is memory: in the worst case a trie can use O(alphabet_size * total_characters) space, though shared prefixes and compressed variants (radix trees) reduce this considerably in practice.
Cricket analogy: Looking up any surname in the trie costs O(m) time and O(1) extra space, where m is the name's length, regardless of how many thousands of players are indexed — beating a balanced BST's O(m log n) comparison cost; the tradeoff is memory since the tree of letter-nodes can grow large with a diverse squad database.
Key Takeaways
- A trie stores strings character-by-character along root-to-node paths, letting keys share prefix edges.
- Insert, search, and starts_with all run in O(m) time, where m is the key length — independent of the number of stored keys.
- A boolean end-of-word flag on each node distinguishes a stored word from a mere prefix of a longer word.
- Tries are ideal for autocomplete, prefix matching, spell-check, and IP/longest-prefix routing.
- Space usage can be high for sparse alphabets; compressed tries (radix trees) mitigate this by merging single-child chains.
Practice what you learned
1. What is the time complexity of searching for a key of length m in a trie containing n keys?
2. In the TrieNode class shown, what does the is_end_of_word flag indicate?
3. Why can trie.search('ca') return False even though trie.starts_with('ca') returns True after inserting 'car'?
4. Which application is a trie particularly well-suited for compared to a hash table?
5. What is the main space tradeoff of a naive trie implementation?
Was this page helpful?
You May Also Like
Binary Search Trees
A binary tree variant that maintains an ordering invariant, enabling fast search, insert, and delete operations.
Hash Tables
A data structure that maps keys to values using a hash function for near-constant time lookups, insertions, and deletions.
Strings as Data Structures
How strings behave as immutable sequences of characters and what that means for performance in Python.