Tries (prefix trees)

The problem: questions about prefixes

When you type "ban" into a shopping app's search box, it suggests "banana", "bangles" and "bandage" before you finish. The question is not "is this exact word stored?" but "which stored words START with these letters?". A set answers the first question in O(L) time (hashing a word of length L), but it cannot answer the second without checking every word. With N words, scanning costs O(N × L) per keystroke.

What a trie is

A trie (from "retrieval", usually said like "try") is a tree where each edge stands for one character. The path from the root to a node spells a prefix. Each node has a children map (a dictionary from character to child node) and an end flag (often called is_end) that says "a complete word ends here".

Words that share a prefix share the same path. After inserting "car", "cat" and "do", the root has two children, c and d. The path c → a is shared by "car" and "cat", and only then splits into r and t.

(root)
 ├─ c
 │   └─ a
 │       ├─ r   (end of "car")
 │       └─ t   (end of "cat")
 └─ d
     └─ o       (end of "do")

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

root = TrieNode()

def insert(word):
    node = root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
    node.is_end = True

for w in ["car", "cat", "do"]:
    insert(w)
print(sorted(root.children))                              # Output: ['c', 'd']
print(sorted(root.children["c"].children["a"].children))  # Output: ['r', 't']

Search versus starts_with

Both operations walk down from the root, one character at a time. If a character is missing, the answer is False. The difference is at the end. search(word) needs is_end to be True at the last node, because "ca" is a path in the trie above but not a stored word. starts_with(prefix) only needs the walk to succeed: "ca" is a prefix of "car".

Cost

Insert, search and starts_with each visit at most L nodes for a word or prefix of length L, so each is O(L) time, and the number of stored words does not matter. Space is the catch. In the worst case every character of every word is its own node, so a trie holds up to O(total characters) nodes, and in Python each node is an object with its own dictionary. A trie of a million short words can use many times the memory of a set holding the same words. Compact versions use an array of 26 children for lowercase letters, or merge chains of single children into one edge (a radix tree).

Autocomplete

To suggest words for a prefix, first walk down to the prefix node (O(L)). Then run a DFS below it and collect every node whose is_end is True, building the word as you go. If you visit the children in sorted order, the words come out in alphabetical order, so you can stop as soon as you have k of them. Real search boxes rank suggestions by popularity or by what you searched before, often by keeping the top few suggestions at each node, but the walk-then-collect idea is the same.

Longest common prefix

The longest common prefix of a list of words is the longest start that all of them share: "fl" for "flower", "flow" and "flight". With a trie, insert all the words and walk down from the root while the current node has exactly one child and is not the end of a word. Without a trie there is a neat trick: the common prefix of all the words equals the common prefix of the alphabetically smallest and largest words.

words = ["flower", "flow", "flight"]
a, b = min(words), max(words)
i = 0
while i < len(a) and a[i] == b[i]:
    i += 1
print(a[:i])   # Output: fl

Common mistakes

• Forgetting the end flag, so search("ca") returns True after inserting only "car". Fix: set is_end at the last node of insert and check it in search.
• Using a mutable default argument such as def __init__(self, children={}), which makes every node share ONE dictionary. Fix: create self.children = {} inside __init__.
• Storing the trie as a class attribute, so two Trie objects share the same words. Fix: create the root in __init__.
• Collecting autocomplete results without sorting the children, then sorting a huge list at the end. Fix: visit children in sorted order and stop at k.
• Using a trie when only exact lookups are needed. Fix: a set is simpler and smaller.