Trie

Trie (Prefix Tree)

Use when: Prefix search, autocomplete, word dictionary with prefix queries.

Complexity: O(L) per insert/search where L = word length

Standard Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_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.is_end = True
 
    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end
 
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

With Count (for frequency)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0  # number of words passing through
 
class Trie:
    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.count += 1

Signals in a Problem

• “Find all words with prefix…”
• Word search / autocomplete
• “How many words start with…”
• XOR problems (binary trie)