Tries

Overview

A trie (prefix tree) stores strings as paths of characters from a root, so words sharing a prefix share nodes. Insert, search, and prefix checks all run in O(m) time where m is the length of the key, independent of how many words are stored. This makes tries ideal for autocomplete and dictionary lookups, trading extra memory for prefix-query speed that a hash table cannot match.

Syntax / Usage

Each node holds a map of child characters plus a flag marking the end of a word.

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):          # O(m)
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word):          # O(m)
        node = self._find(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):   # O(m)
        return self._find(prefix) is not None

    def _find(self, chars):
        node = self.root
        for ch in chars:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Examples

Build a small dictionary and query exact words versus prefixes:

trie = Trie()
for word in ["cat", "car", "card", "dog"]:
    trie.insert(word)

print(trie.search("car"))       # True
print(trie.search("ca"))        # False - prefix, not a full word
print(trie.starts_with("ca"))   # True

Collect every word that shares a given prefix, useful for autocomplete:

def autocomplete(trie, prefix):
    node = trie._find(prefix)
    results = []
    if node is None:
        return results

    def dfs(current, path):
        if current.is_word:
            results.append(prefix + path)
        for ch, child in current.children.items():
            dfs(child, path + ch)

    dfs(node, "")
    return results

print(autocomplete(trie, "car"))  # ['car', 'card']

Common Mistakes

• Forgetting the is_word flag, which makes prefixes indistinguishable from stored words
• Assuming a matched path means the word exists — you must also check is_word
• Overusing tries for small datasets where a hash set is simpler and lighter
• Ignoring the high memory cost when alphabets are large or words share few prefixes
• Mutating the shared root incorrectly when deleting, leaving orphaned or broken paths

See Also

data-structures-trees data-structures-hash-tables data-structures-graphs-representation