Tries (Prefix Trees)

When you type "ca" into a search box and it instantly suggests "cat" and "car", something has to find every word that starts with those two letters — fast. A trie (say "try"), also called a prefix tree, is the data structure built for exactly that. Instead of storing whole words, it stores them letter by letter, so words that share a prefix share a path.

The idea

A trie is a tree where each edge is one letter. To store a word, you walk down from the root, one node per letter, creating a child node whenever the next letter is missing. The last letter's node gets a flag that says "a real word ends here".

The magic is prefix sharing. "cat" and "car" both start with "ca", so they walk the same two nodes and only split at the third letter. Storing 1,000 words that all start with "pre" costs you that "p-r-e" path exactly once.

To answer "do any words start with this prefix?", you do the same walk — but you create nothing. If you can follow every letter of the prefix without falling off the tree, the prefix exists, and everything below that node is a suggestion.

Walk through it

Press Play on the right, or step with Next / Back.

• Insert "cat": there is no "c" under the root, so we create c, then a, then t. The final node t turns green with a check — that marks the end of a real word.
• Insert "car": "c" and "a" already exist, so we just walk into them (no new nodes). Only "r" is new. Now the single "ca" path feeds two words.
• startsWith("ca"): we start at the root and follow c, then a. Both exist, so the prefix is there. The whole subtree below "a" lights up green — those are the words to suggest.

The code panel highlights the matching line: the for loop and setdefault while inserting, the if ch not in node check while searching.

The code, line by line

class Trie:
    def __init__(self):
        self.root = {}
 
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True   # mark word end
 
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return False
            node = node[ch]
        return True

• Each node is just a dictionary mapping a letter to a child node. The root is an empty dict.
• setdefault(ch, {}) is the whole trick of insert: if the child ch already exists it returns it, otherwise it creates an empty child and returns that. Either way node moves down one letter.
• node["$"] = True marks a word end. We use a special key "$" (which can never be a letter) so we can tell "cat" the word apart from "cat" being just a prefix of "category".
• starts_with walks the prefix and returns False the moment a letter is missing. If it survives the whole loop, the prefix exists.

Complexity

Notice what is not in that table: the number of words, n. A trie's lookup time depends only on the length of the word or prefix, not on how many words you have stored. Searching for a 4-letter prefix takes 4 steps whether the trie holds 10 words or 10 million. That is why autocomplete stays fast as the dictionary grows.

The space cost is the total number of letters across all words — but shared prefixes are stored only once, so in practice a trie over real words is much smaller than storing every word in full.

When to use / pitfalls

Practice