Trie (Prefix Tree)
DSA · Trees
Theory
A trie stores strings character by character, where each node represents a prefix and children are the possible next characters. Inserting or searching a word of length L takes O(L), independent of how many words are stored. A flag marks nodes where a complete word ends, and walking to a prefix node lets you list every word that starts with it.
Why we use it
Tries make prefix searches and autocomplete very fast and share storage between words with common prefixes.
When to use it
Use a trie for autocomplete, spell checking, dictionary lookups, IP routing tables and word-search puzzles.
How it works
- Start at root
- For each character of the word
- Child for this char exists? Yes: Move to it. No: Create child, move to it.
- Mark last node as end-of-word
- Prefix search follows the same path
Syntax
class TrieNode:
def __init__(self): self.children = {}; self.end = False
insert(word): walk/create nodes for each char; mark end
starts_with(prefix): walk the prefix; collect words below
Time: O(L) per word Space: O(total characters)Example
class TrieNode:
def __init__(self):
self.children = {}
self.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.end = True
def suggest(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
out = []
def collect(n, path):
if n.end:
out.append(path)
for ch in sorted(n.children):
collect(n.children[ch], path + ch)
collect(node, prefix)
return out
t = Trie()
for w in ["sql", "snowflake", "spark", "sigma", "python", "pyspark"]:
t.insert(w)
print("Suggestions for 's':", t.suggest("s"))
print("Suggestions for 'py':", t.suggest("py"))Key points
- Each node is a prefix
- O(L) insert and search
- Ideal for autocomplete
- Can use more memory than a hash set