Tries (Prefix Trees)

A hash set can tell you whether an exact word exists, but it is useless the moment a question mentions prefixes — “does any word start with app?”, “autocomplete this”, “find the longest word buildable one letter at a time”. That is the trie’s home turf, and it is a small, elegant structure once you see it.

The idea

A trie (pronounced “try”, from re-trie-val) is a tree where each edge is labelled with a character. A word is a path from the root; a boolean marker on the final node says “a word ends here”. Because cat and car share the prefix ca, they share that path and only diverge at the last letter. Insert and search both cost O(length of the word) — crucially, this does not depend on how many words are already stored, which is what makes prefix queries fast.

In Python the cleanest implementation is a dict of dicts, using a sentinel key (here '$') to mark the end of a word — no node class required.

Worked example: implement a trie

The three core operations — insert, search (exact), and startsWith (prefix) — are almost the same walk down the tree:

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.setdefault(c, {})   # create the child if missing
        node['$'] = True                    # mark end of a word
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node: return False
            node = node[c]
        return '$' in node                  # exact match only if a word ends here
    def startsWith(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node: return False
            node = node[c]
        return True                         # the path exists → some word has this prefix
# Trie().insert("apple"); search("apple") -> True; search("app") -> False; startsWith("app") -> True

The only difference between search and startsWith is the final line: an exact search demands a word-end marker, a prefix search just needs the path to exist.

Supporting wildcards

Add a single branch and the same structure handles . wildcards (the classic “Add and Search Word” problem): at a ., recurse into every child instead of one.

def search(self, word):
    def dfs(node, i):
        if i == len(word): return '$' in node
        c = word[i]
        if c == '.':
            return any(dfs(node[k], i + 1) for k in node if k != '$')
        return c in node and dfs(node[c], i + 1)
    return dfs(self.root, 0)

The bit-trie trick

Tries are not only for letters. Store each number as a 32-bit path (most significant bit first) and you get a bit trie, which solves maximum XOR problems: to maximise a ^ b, walk the trie greedily always taking the opposite bit when it exists, because a differing bit contributes a 1 to the XOR at that position.

def findMaximumXOR(nums):
    root = {}
    for num in nums:                        # insert every number as a 32-bit path
        node = root
        for i in range(31, -1, -1):
            b = (num >> i) & 1; node = node.setdefault(b, {})
    best = 0
    for num in nums:                        # for each number, greedily pick opposite bits
        node = root; cur = 0
        for i in range(31, -1, -1):
            b = (num >> i) & 1; want = 1 - b
            if want in node: cur |= (1 << i); node = node[want]
            else:            node = node[b]
        best = max(best, cur)
    return best
# findMaximumXOR([3,10,5,25,2,8]) -> 28

Step-by-step walkthrough

Trace a trie as we insert car, cat, cart and then query it. Shared prefixes reuse existing nodes, and an end-of-word marker ($) distinguishes a stored word from a mere prefix.

Note search("ca") is False (no word ends there) but startsWith("ca") is True — the end marker is the only difference. Every operation costs O(length of the word), regardless of how many words are stored.

When to reach for it

Signals: “prefix”, “starts with”, “autocomplete / typeahead / suggestions”, “dictionary of words”, “search with . wildcards”, or “maximum XOR pair”. More generally, reach for a trie whenever you need to query many strings by shared prefix rather than by exact value — a hash set can do exact membership, but only a trie makes prefixes cheap. It is also the backbone of the Typeahead system-design problem.

Pitfalls

• Forgetting the end marker. Without a per-node “word ends here” flag, you cannot tell a stored word from a mere prefix — search("app") would wrongly return true just because apple exists.
• Memory. A trie can use a lot of pointers for sparse, long strings. Mention that an array-of-26-children node is faster but heavier than a dict; a dict is usually fine in an interview.
• Using a trie when a set suffices. If the problem only ever asks for exact membership and never prefixes, a hash set is simpler and faster. The trie earns its keep on prefix work.

Recap

A trie stores strings as a character-keyed tree so shared prefixes share a path, giving O(word length) insert and search independent of the number of words. Build it as a dict of dicts with a sentinel end-marker; search needs the marker, startsWith just needs the path. A .-wildcard is one DFS branch away, and storing numbers bit-by-bit turns the same structure into a bit trie for maximum-XOR problems. Signal: prefix, starts-with, autocomplete, word dictionary.

Practice: 10 solved problems on tries → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 21 — Bit Manipulation.