Tries (Prefix Trees)

A trie (pronounced “try”, short for retrieval tree) is a tree-shaped data structure built specifically for storing and searching strings. Instead of comparing whole strings against each other the way a list or hash set does, a trie breaks each string into its characters and shares common prefixes across a tree, so words like car, card, and care all reuse the same c-a-r path. This makes tries extremely fast for prefix-based queries — autocomplete, spell-checkers, IP routing tables, and word games all lean on this structure because it can answer “does anything start with X?” in time proportional to the length of X, not the number of words stored.

Overview / How it works

Imagine you’re building the search suggestions for an e-commerce site. A shopper types app and you need to instantly show “apple watch”, “apple airpods”, and “appliance parts”. A hash set gives you O(1) exact-match lookups, but it has no idea which of its thousands of entries start with app — you’d have to scan every single entry, an O(n) operation regardless of how short the prefix is. A trie solves exactly this problem by organizing strings so that shared prefixes are shared paths through a tree.

Every trie has a root node representing the empty string. Each node holds a mapping from “next character” to “child node”, plus a flag — typically called is_end_of_word — marking whether the path from the root to this node spells out a complete word that was actually inserted (as opposed to merely being a prefix of some longer word). To insert a word, you start at the root and walk one character at a time: if the current node already has a child for that character, follow it; if not, create a new child node and follow that. When you run out of characters, you mark the final node as is_end_of_word = True. To search for a word, you do the same walk — if at any point the required character doesn’t exist among the current node’s children, the word (or even the prefix) isn’t in the trie, so you can stop early and return False. If you make it to the end of the walk, the word is present only if the final node’s is_end_of_word flag is set; simply reaching a node isn’t enough, because that node might just be a waypoint on the way to a longer word.

This last point trips a lot of people up: after inserting car, the path c-a-r exists in the trie, but the path c-a also exists (it’s a prefix of that same path) even though “ca” was never inserted as its own word. A correct search must check the end-of-word flag; a correct starts_with/prefix check should not.

Nodes are commonly implemented with a Python dict mapping character → child node, which only allocates entries for characters that are actually used — ideal when the alphabet is large (Unicode) or sparse. An alternative implementation uses a fixed-size array (e.g., length 26 for lowercase English letters) indexed by ord(char) - ord('a'); this trades memory (every node always reserves 26 slots, used or not) for slightly faster, hashing-free access, and only makes sense when the alphabet is small and fixed.

Time and Space Complexity

Let m be the length of the word or prefix being inserted/searched, and N be the number of words stored in the trie. The defining property of a trie is that most operations depend only on m, not on N — unlike scanning a list of strings, where cost grows with how many strings you have stored.

Operation	Time Complexity	Why
insert(word)	O(m)	Visits or creates exactly one node per character of word.
search(word)	O(m)	Walks one node per character; can exit early on a missing character.
starts_with(prefix)	O(m)	Same walk as search, just without checking the end-of-word flag at the end.
delete(word)	O(m)	One walk down to find the word, one walk back up to prune now-useless nodes.
Collect all words with a prefix	O(m + k)	O(m) to reach the prefix’s node, then O(k) to depth-first traverse the k characters across all matching words.

Space complexity is O(total characters stored across the trie), which in the worst case (no words share any prefixes) is O(N · L) for N words of average length L — effectively the same as storing every word separately. In practice it’s usually much better than that, because every shared prefix is stored once instead of once per word; a trie holding “car”, “card”, and “care” only pays for the “c-a-r” path a single time. An array-based (fixed alphabet) trie instead uses O(ALPHABET_SIZE) space per node regardless of how many children are actually populated, which can waste memory on sparse tries — another reason dict-backed children are usually the safer default.

Examples

Example 1: Insert and search

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, "TrieNode"] = {}
        self.is_end_of_word: bool = False


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

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def _find_node(self, prefix: str) -> "TrieNode | None":
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node


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

print(trie.search("car"))
print(trie.search("ca"))
print(trie.starts_with("ca"))
print(trie.search("card"))
print(trie.starts_with("do"))
print(trie.search("dog"))
print(trie.search("dogs"))

Output:

True
False
True
True
True
True
False

After inserting all five words, the path c-a-r ends at a node with is_end_of_word = True (because “car” was inserted directly), so search("car") is True. The path c-a also exists in the tree, but no node there is flagged as an end of word, so search("ca") correctly returns False even though starts_with("ca") returns True. search("dogs") fails because after following d-o-g, there is no child for s — the walk falls off the tree and _find_node returns None.

Example 2: Autocomplete — collecting all words with a prefix

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, "TrieNode"] = {}
        self.is_end_of_word: bool = False


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

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children.setdefault(char, TrieNode())
        node.is_end_of_word = True

    def _find_node(self, prefix: str) -> "TrieNode | None":
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def words_with_prefix(self, prefix: str) -> list[str]:
        results: list[str] = []
        start_node = self._find_node(prefix)
        if start_node is None:
            return results
        self._collect(start_node, prefix, results)
        return results

    def _collect(self, node: "TrieNode", path: str, results: list[str]) -> None:
        if node.is_end_of_word:
            results.append(path)
        for char, child in sorted(node.children.items()):
            self._collect(child, path + char, results)


trie = Trie()
for word in ["app", "apple", "application", "apt", "banana"]:
    trie.insert(word)

print(trie.words_with_prefix("app"))
print(trie.words_with_prefix("ap"))
print(trie.words_with_prefix("ban"))
print(trie.words_with_prefix("xyz"))

Output:

['app', 'apple', 'application']
['app', 'apple', 'application', 'apt']
['banana']
[]

_find_node walks to the node representing the prefix in O(m) time, then _collect depth-first-searches only the subtree under that node, visiting each matching word’s characters once. Sorting each node’s children before recursing guarantees results come back in alphabetical order — note that dict insertion order (guaranteed since Python 3.7) is not the same as sorted order, so relying on plain iteration instead of sorted() would be a subtle bug here. words_with_prefix("xyz") returns an empty list immediately because _find_node can’t even complete the walk to “xyz”.

Example 3: Prefix counts without a full traversal

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, "TrieNode"] = {}
        self.is_end_of_word: bool = False
        self.prefix_count: int = 0


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

    def insert(self, word: str) -> None:
        node = self.root
        node.prefix_count += 1
        for char in word:
            node = node.children.setdefault(char, TrieNode())
            node.prefix_count += 1
        node.is_end_of_word = True

    def count_words_with_prefix(self, prefix: str) -> int:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.prefix_count


trie = Trie()
for word in ["dog", "door", "dorm", "dog", "dot"]:
    trie.insert(word)

print(trie.count_words_with_prefix("do"))
print(trie.count_words_with_prefix("dor"))
print(trie.count_words_with_prefix("dog"))
print(trie.count_words_with_prefix("cat"))

Output:

5
1
2
0

Each node tracks how many inserted words pass through it. All five inserted words (“dog”, “door”, “dorm”, “dog” again, “dot”) start with do, so that node’s prefix_count is 5. Only “dorm” has the prefix dor (“door”‘s third character is o, not r), so that count is 1. “dog” was inserted twice, so its node’s count is 2. This avoids the O(k) subtree traversal from Example 2 entirely — counting is a pure O(m) walk because the bookkeeping happens during insertion instead of at query time.

How it works step by step

Trace inserting ["to", "tea", "ted", "ten"] into an empty trie, one word at a time:

Insert “to”: from root, create child t, move to it; create child o under t, move to it; mark that o node as end-of-word.

Insert “tea”: from root, t already exists, reuse it; under t, e doesn’t exist yet, create it; under e, create a; mark a as end-of-word. The tree now branches at the t node into two children, o and e.

Insert “ted”: t exists, reuse; e exists (from “tea”), reuse; under e, d doesn’t exist, create it; mark d as end-of-word. Now the e node (under t) branches into a and d.

Insert “ten”: t and e both exist, reuse both; under e, n doesn’t exist, create it; mark n as end-of-word. The e node now has three children: a, d, n.

Now trace two queries. search("tea"): walk t → e → a, all exist; the final a node has is_end_of_word = True, so the result is True. search("te"): walk t → e, both exist, but the e node itself was never marked as end-of-word (only its children a, d, n were) — so the result is False. starts_with("te"), by contrast, only checks that the walk completes without falling off the tree, so it correctly returns True.

Common Mistakes

Mistake 1: Treating “path exists” as “word exists”

A tempting but wrong shortcut is to implement search exactly like a prefix check, forgetting the end-of-word flag entirely:

def search(self, word: str) -> bool:
    node = self.root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return True  # BUG: True even if `word` is only a prefix, never actually inserted

With this version, after inserting only “card”, calling search("car") would incorrectly return True — “car” was never inserted, only “card” was, but the path c-a-r happens to exist because it’s a prefix of “card”. The fix is to check the flag on the final node instead of just confirming the walk completed:

def search(self, word: str) -> bool:
    node = self.root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end_of_word

Mistake 2: Mutable default argument in a recursive collector

When writing a recursive helper that accumulates results (very common for the words-with-prefix traversal), it’s easy to reach for a default argument as the accumulator:

def collect_words(node: "TrieNode", path: str = "", results: list[str] = []) -> list[str]:
    if node.is_end_of_word:
        results.append(path)
    for char, child in node.children.items():
        collect_words(child, path + char, results)
    return results

Python evaluates default argument values exactly once, when the function is defined — not once per call. That empty list is created a single time and then reused (and mutated) across every top-level call to collect_words, so a second unrelated call will still contain words appended during the first call. The fix is the standard “sentinel default” pattern: default to None and create a fresh list inside the function body.

def collect_words(node: "TrieNode", path: str = "", results: "list[str] | None" = None) -> list[str]:
    if results is None:
        results = []
    if node.is_end_of_word:
        results.append(path)
    for char, child in node.children.items():
        collect_words(child, path + char, results)
    return results

Best Practices

• Reach for a trie when you need repeated prefix queries (autocomplete, spell-check, “starts with” search); for simple exact-membership checks, a plain set or dict is simpler and just as fast.
• Prefer dict-based children unless the alphabet is small and fixed and you need to squeeze out the last bit of performance — a fixed-size array (e.g., length 26) avoids dict hashing overhead but wastes memory on unused slots.
• Always separate “a path exists” from “a word was inserted” with an explicit end-of-word flag; this is the single most common source of bugs in trie code.
• Store extra data at nodes (counts, a payload value, a rank) to answer richer queries in O(m) instead of re-walking a subtree in O(m + k) every time, as shown in Example 3.
• For very large dictionaries, consider a compressed trie (a.k.a. radix/Patricia trie), which merges chains of single-child nodes into one edge holding a substring — it trades some code complexity for significantly less memory overhead.
• When implementing delete, prune nodes bottom-up after removing the end-of-word flag: a node can be deleted only if it has no children and is not itself the end of another word.
• Normalize input consistently (e.g., always lowercase) at both insert and search time if the trie should be case-insensitive.
• Never use a mutable default argument (like results=[]) as an accumulator in a recursive trie traversal — default to None and initialize inside the function.

Practice Exercises

• Delete with pruning: Add a delete(word) method to the Trie class from Example 1. It should unset is_end_of_word for the target word and also remove any now-useless nodes (nodes with no children that aren’t the end of some other word), walking back up toward the root. Hint: write it recursively, and prune a child only after its own recursive call reports that it became empty.
• Longest common prefix: Given a list of strings such as ["flower", "flow", "flight"], insert them all into a trie, then find the longest common prefix shared by every string by walking down from the root as long as each node has exactly one child and is not itself an end-of-word. For the example list, the expected output is "fl".
• Top-k autocomplete: Using words_with_prefix from Example 2, write a function that, given a prefix and a value k, returns at most the first k alphabetically-sorted matches. Test it against a word list of your choice and confirm it returns fewer than k results when fewer matches exist.

Summary

• A trie stores strings as shared paths through a tree, one character per edge, so common prefixes are stored once instead of once per word.
• Every node needs a way to distinguish “this is just a prefix” from “this is a complete stored word” — typically an is_end_of_word boolean flag.
• insert, search, and starts_with are all O(m), where m is the length of the word/prefix — independent of how many words N are stored in the trie.
• Collecting all words under a prefix costs O(m + k): O(m) to reach the prefix node, O(k) to traverse the k characters across all matches.
• Space is roughly O(total characters stored), much less than storing every word independently whenever words share prefixes.
• Dict-based children generalize to any alphabet and save memory on sparse tries; fixed-size array children are faster but only sensible for small, fixed alphabets.
• Watch for two classic bugs: forgetting the end-of-word flag (turning search into starts_with by accident), and using a mutable default argument as a recursive accumulator.
• Tries shine specifically for prefix-shaped problems — autocomplete, spell-checking, IP routing, word games — and are usually overkill for simple membership testing, where a hash set already gives O(1) average lookups.