Trie Concept

A trie (prefix tree) is great for prefix searching.

Real examples:

• autocomplete
• dictionary word search
• spam filters (prefix rules)

Trie node structure

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

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