Trie Concept
Learn trie (prefix tree) for fast prefix searches like autocomplete. Build a simple trie and understand why it beats scanning lists for prefixes.
A trie (prefix tree) is great for prefix searching. Real examples: - autocomplete - dictionary word search - spam filters (prefix rules) ## Trie node structure ```python class TrieNode: def __init__(self): self.children = {} self.is_end = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: node = self.root for ch in word: node = node.children.setdefault(ch, TrieNode()) node.is_end = True def starts_with(self, prefix: str) -> bool: node = self.root for ch in prefix: if ch not in node.children: return False node = node.children[ch] return True trie = Trie() trie.insert("cat") trie.insert("car") print(trie.starts_with("ca")) # True print(trie.starts_with("cb")) # False ``` ## Graph: trie prefix idea ```mermaid flowchart TD A[root] --> B[c] B --> C[a] C --> D[t] C --> E[r] ``` ## Remember - trie is built for prefixes - great for many words and frequent prefix queries - not always needed in normal apps, but powerful in search features