Tries & Search-as-you-type
Type "ne" into Tunebox's search box and suggestions should appear before the next
keystroke. Checking title.startswith("ne") against every title works for a few
hundred songs, but with millions, every keystroke rescans the lot. A trie (usually
said "try", from retrieval) lets titles that start alike share the same path, so a prefix
is found in as many steps as it has characters.
One character per edge
A trie is a tree whose edges are characters. Every title is a path down from the root, and titles that begin the same way share the start of that path. Each node holds a dict of children and a flag saying whether a title ends there:
root ─ n ─ e ─┬─ o● ─ n● ● = a title ends here
└─ t● titles: neo, neon, net❓ Cross-question — "Why the
is_endflag? If the path exists, isn't it a title?" No. Inserting "neon" creates the path n-e-o on its way down, but "neo" is only a title if someone inserted it. Without the flag, every prefix of every title would pass as a title too.
search and starts_with
Both walk down one character at a time and give up the moment a character is missing. They differ only in the question they ask at the end:
class TrieNode:
def __init__(self):
self.children, self.is_end = {}, False
def walk(root, text):
node = root
for ch in text:
if ch not in node.children:
return None
node = node.children[ch]
return node
root = TrieNode()
node = root
for ch in "neon":
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
found = walk(root, "neo")
print(found is not None and found.is_end, found is not None)So search(word) is node is not None and node.is_end, while starts_with(prefix)
is just node is not None. Each costs O(m) for m characters, no matter how many titles
the trie holds.
Tries as nested dicts
Python's dicts make a very compact trie: every node is a dict, and a special key marks the end of a title. Step through two inserts and watch the structure grow:
setdefault(ch, {}) returns the child if it exists, and otherwise creates it and
returns that — a whole insert in three lines. The class version is clearer and easier
to extend with extra fields; you'll see the dict version in quick scripts and interviews.
Collecting completions
To suggest titles, walk to the prefix's node, then go depth-first through everything below it, adding a letter at each step. Visit children in sorted order and the titles come out alphabetically, with no sort at the end. This version loses titles:
Every title starting with "ne" should be listed, but "neon" is missing, because the walk stops too early.
Why is that DFS order alphabetical? A title ending at a node is recorded before anything longer below it, and Python compares strings the same way:
print(sorted(["neon", "neo lights", "neo"]))Coming from Java/JS: a
Map<Character, TrieNode>, or a JSMapper node, is the same design. Many Java tutorials use a fixedTrieNode[26]array instead — faster for lowercase a–z, and useless the moment a title contains a space, a digit or "é".
Tries vs a sorted list with bisect
A trie isn't the only way to answer prefix questions. Sort the titles once, and all the
titles starting with "ne" sit in one unbroken block — bisect finds where it begins:
That costs O(p log n) per query and almost no extra memory. The price is insertion: adding a title shifts the list, O(n). A trie flips the trade-off. An insert is only O(m), but every character may get its own node with its own dict — easily tens of times the memory of the strings themselves.
❓ Cross-question — "So when is a trie actually worth it?" When titles change often; when nodes carry useful data, like how many titles pass through or the best few suggestions; or when queries branch, as in wildcards and spell-checking. For a static list you search now and then,
bisectwins.
| Operation | Trie | Sorted list + bisect |
|---|---|---|
| Insert a title of length m | O(m) | O(n) — items shift |
| Exact search | O(m) | O(m log n) |
| Find the block for a prefix of length p | O(p) | O(p log n) |
| List the k matches | O(size of that subtree) | O(k · p) |
| Memory | a node per distinct prefix | just the strings |
Idioms & real-world patterns
Counting at every node
Keep a counter on each node and add 1 on the way down during insert. "How many titles start with ne?" then costs O(p), with no subtree walk:
Real autocomplete goes one step further and keeps the top few suggestions on each node, updated as titles are inserted, so a keystroke returns ranked results immediately. Routers use tries to match IP address prefixes, and spell-checkers use them to explore near-miss words.
⚡ Advanced — radix trees
Long chains of single-child nodes waste memory. A radix tree, or compressed trie,
merges each such chain into one edge labelled with a whole string, such as "eon".
Lookups work the same way, with far fewer nodes.
🎯 Your turn
Write suggest_titles(titles, prefix, limit). Build a trie from titles (Tunebox
stores them lowercase), walk to prefix, and return up to limit titles that start
with it, alphabetically, each title once:
suggest_titles(["neon", "nebula", "night drive", "needle", "nectar"], "ne", 3)→["nebula", "nectar", "needle"]suggest_titles(["neon", "nebula"], "x", 5)→[]
Hint — insert every title, then walk the prefix and return [] if a character is
missing. Finish with a DFS over sorted children that stops once it has limit titles.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅