Tries, radix trees and autocomplete | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython example pack ↓

A trie follows characters or bits along branches. A terminal marker distinguishes a stored word from a prefix. Autocomplete finds the prefix node then traverses descendants; output count and total output length belong in its cost.

Dense alphabet arrays are fast but waste space on sparse data; dictionaries offer flexibility. Radix/Patricia trees compress single-child paths into labelled edges. Deletion clears terminals and prunes nodes unused by other words.

Unicode characters, code points and graphemes differ; define normalisation and case folding. Popularity-ranked suggestions require frequencies or top-k metadata rather than plain alphabetical traversal. Compare trie and hash-map costs using key length L.

A worked trace

car,cart,cat share c→a; r is terminal and has terminal childt. Prefix ca yields three words.

Cost and assumptions

With constant child lookup, insert/search O(L); autocomplete costs prefix length plus traversal/output size.

Executable example

Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.

Python 3

END = object()
root = {}
for word in ["car", "cart", "cat"]:
    node = root
    for c in word: node = node.setdefault(c, {})
    node[END] = True

def contains(word):
    node = root
    for c in word:
        if c not in node: return False
        node = node[c]
    return END in node
assert contains("car") and not contains("ca")

TEST YOUR UNDERSTANDING

Your turn

Where is the terminal stored if empty strings are supported?

Reveal the reasoning

At the root. Empty-key support is part of the contract; implementations either reject it or use a root terminal.

Take it further

Write down the input contract and the invariant before changing the example.
Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
Derive the cost under the stated model; measure several input sizes and explain discrepancies.

Primary reading & lecture notes

Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.

Princeton · Algorithms, Sedgewick & Wayne ↗Pat Morin · Open Data Structures ↗

Solve the exercise before moving on.

RasimAtaberkŞahin