Trie

Words as paths

Each word is a path from the root, one edge per character. cat and car share the c-a path then branch. Lookup, insert, and prefix checks are O(L) where L is the word length — independent of how many words are stored.

Insert & search

A node is just a map of child characters plus an end-of-word flag.

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.setdefault(c, {})
        node['$'] = True          # word ends here
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node: return False
            node = node[c]
        return '$' in node

Phone contacts

Type 'Jo' and the phone instantly narrows to John, Joanna, Joseph. It's walked two edges down a trie of names.

Where it hides

Autocomplete, spell-check, IP routing tables, and word-search / prefix problems. Trade-off: heavy pointer overhead per character.