Trie — Explained with Examples
A trie (prefix tree) is a tree data structure for storing strings, enabling efficient prefix-based searches like autocomplete and spell checking.
A trie (pronounced “try”) stores strings character by character. Each node represents a character, and paths from root to leaf form complete strings. Nodes typically have a boolean flag marking the end of a word and an array or map of child nodes. Searching for a word of length k takes O(k) time, independent of the number of stored strings — much faster than a hash table for prefix queries.
Think of a trie like a phone keypad contact search. As you type “Joh”, the phone shows “John”, “Johnson”, “Johansson” — every contact starting with those letters. A trie works the same way: following characters down the tree reveals all words sharing that prefix.
Tries are used in autocomplete systems, spell checkers, IP routing (longest prefix matching), and word games like Boggle solvers.
class Trie:
class Node:
def __init__(self):
self.children = {}
self.is_end = False
def __init__(self):
self.root = self.Node()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = self.Node()
node = node.children[char]
node.is_end = True
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_end
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
def autocomplete(self, prefix):
def _collect(node, path, results):
if node.is_end:
results.append(prefix + path)
for char, child in sorted(node.children.items()):
_collect(child, path + char, results)
node = self.root
for char in prefix:
if char not in node.children:
return []
node = node.children[char]
results = []
_collect(node, "", results)
return results
trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("apricot")
print(trie.search("app")) # True
print(trie.starts_with("apr")) # True
print(trie.autocomplete("ap")) # ['apricot', 'app', 'apple']Tries trade memory for speed. A compressed trie (radix tree) reduces memory by merging nodes with single children.
Hash Table, Tree, Binary Tree, DFS
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro