19. Trie

What you'll learn

• 1Implement a trie node
• 2Insert and search words
• 3Detect when one word is a prefix of another

Overview

A trie node has a children dict (keyed by character) and an 'is_word' flag. Operations are O(L) where L is the string length — independent of how many strings are stored.

Core Concepts

1. Trie node

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

2. Insert

def insert(root, word):
    cur = root
    for c in word:
        if c not in cur.children:
            cur.children[c] = TrieNode()
        cur = cur.children[c]
    cur.is_word = True

3. Search

def search(root, word):
    cur = root
    for c in word:
        if c not in cur.children: return False
        cur = cur.children[c]
    return cur.is_word

def starts_with(root, prefix):
    cur = root
    for c in prefix:
        if c not in cur.children: return False
        cur = cur.children[c]
    return True

4. Prefix conflict detection

Used in BOJ 5052 (Phone list): check whether any phone number is a prefix of another.

def insert_check(root, word):
    """Return False if word is prefix of/contains another word in the trie."""
    cur = root
    for c in word:
        if cur.is_word: return False        # an earlier word is prefix of this
        if c not in cur.children:
            cur.children[c] = TrieNode()
        cur = cur.children[c]
    cur.is_word = True
    return not bool(cur.children)            # this word is prefix of an existing one

5. Space-time trade-offs

• Memory: up to O(total characters × alphabet size). Use a dict for sparse alphabets, an array for dense.
• Better than hash for prefix queries (hash needs to enumerate all keys to find matches).

Examples

Example 1 — src/01_trie_basic.py

Insert + search + starts_with.

Example 2 — src/02_autocomplete.py

Given a prefix, list all words in the trie that start with it.

Example 3 — src/03_prefix_conflict.py

BOJ 5052 prefix-conflict detection in one pass.

Example 4 — src/04_word_count.py

Count how many strings in a list have a given prefix.

Common Mistakes

1. Forgetting the is_word flag → can't distinguish 'app' from 'apple'.
2. Using only an array of size 26 for alphabet — fails for digits, mixed case.
3. Building a fresh trie per query — build once, query many times.
4. Storing the entire string at each node — wastes memory; just store characters per level.

Recap

• Trie = tree of characters, O(L) per operation.
• Great for prefix queries and autocomplete.
• Watch memory: each node has overhead.

Try It

1. BOJ 14425 (String set).
2. BOJ 5052 (Phone numbers).