Tries
Build prefix trees for dictionary lookup, autocomplete, and prefix queries.
a–z; define a different alphabet and input policy for other text.Objectives: share work between common prefixes
A trie (pronounced “try”) is a rooted tree in which each edge represents one character. A path from the root spells a prefix, and a marker on a node says whether that path is a complete stored word. Words such as car, card, and care reuse their common car path. This makes lookup proportional to query length rather than the number of stored words, at the cost of memory for child links.
1. Node model and representation trade-offs
For a fixed alphabet of 26 lowercase letters, each node can hold 26 child pointers and a Boolean terminal flag. The edge for letter c is stored at index c−'a'. A terminal flag is necessary because both car and card can exist: the node for car is a word and also has a child. Without the flag, a prefix and a complete key become indistinguishable.
Zero-initializing with calloc sets children to null and is_word to false. An array representation is fast and simple, but every node reserves space for all 26 links even if it has one child. A map or sorted edge list saves memory for sparse nodes, but adds lookup overhead. Choose from expected alphabet size, word count, and memory constraints.
2. Insert a word
Start at the root and follow or create one edge per character. Mark the final node as a word. Inserting a word that is already present is idempotent: it ends by setting a flag that is already true. Empty strings can be represented by marking the root itself terminal, if the application allows them.
If allocation fails after part of a path is created, the trie remains structurally valid but may contain nonterminal prefix nodes. Retrying insertion can complete it. If atomic insertion is required, allocate the missing path separately and attach it only after every allocation succeeds. The exact memory-failure guarantee belongs in the API contract.
3. Search words and prefixes
A word search must reach the final node and see is_word. A prefix search only needs to reach the final node, even if it is not terminal. This difference is a frequent source of errors. For example, after inserting card, the query car is a valid prefix, but it is a stored word only if it was inserted separately.
Both lookup operations take O(L) time for a query of length L. They do not scan every stored word. This complexity assumes indexing into a child array is O(1); map-based children may have different costs. An empty prefix reaches the root, so it is present whenever the root exists, even when no words are stored.
4. Autocomplete and delete semantics
Autocomplete first walks to the prefix node, then performs a DFS below it, adding characters to a working buffer and emitting words when a terminal node is reached. To cap results at k, stop after k matches; to return results in alphabetical order, visit child indices from 0 to 25. Listing all matches necessarily costs at least the number of characters emitted. Deletion clears the terminal flag; it should prune a node only if it is nonterminal and has no children, otherwise another word still depends on that path.
| Operation | Work | Important condition |
|---|---|---|
| Insert / exact search | O(L) | Every character must fit the chosen alphabet |
| Prefix lookup | O(L) | The path may exist without being a complete word |
| Enumerate suggestions | O(L + output size) | Bound results to control latency and memory |
| Space | O(total nodes × alphabet) | Array child pointers may be wasteful for sparse tries |
5. Free every allocated node
Each created node owns all descendants reachable from it. A postorder traversal frees children before the parent. Call it once on the root when the complete dictionary is no longer needed; never free a child separately and then traverse it again from the root.
The recursive version is clear for ordinary word depths. If inputs can contain extremely long strings, recursion depth itself becomes a resource concern; use an explicit stack or a bounded input policy. In a long-running service, also consider whether the entire vocabulary fits in memory and how updates are published safely to readers.
6. Capacity planning and text policy
A trie’s node count depends on the number of distinct prefixes, not simply the number of words. If a million words share a long prefix, that prefix is stored once; if the words diverge immediately, many branches are needed. A fixed child array allocates 26 pointers for every node, including leaves. For a large dictionary, measure node count and memory before choosing this representation, and consider a compact edge vector, radix/compressed trie, or memory-mapped static index.
Text policy is part of correctness. This lesson treats input as lowercase single-byte English letters. To support case-insensitive search, normalize before insertion and lookup using the same rules. To support Unicode, code points or grapheme clusters need a deliberate encoding and normalization strategy; a byte-by-byte trie can split a multibyte character and does not automatically implement human-language prefix semantics.
7. Common mistakes
- Confusing a prefix with a stored key: exact search checks the terminal marker; prefix search does not.
- Forgetting to validate characters: indexing
ch - 'a'without checking bounds can read or write outside the child array. - Assuming tries are always smaller or faster: a dense child array can consume far more memory than the raw words; benchmark the actual alphabet and workload.
- Deleting shared paths: clear the terminal marker and prune only nodes that have no children and are not another word.
8. Practice
- Insert
car,card, andcare. Trace the shared path and answer exact-word and prefix queries. - Implement a recursive suggestion collector that writes at most k lowercase words into a caller-provided result buffer.
- Implement deletion and explain why deleting
carmust not erase the path needed bycard. - Extend the input alphabet to digits as well as letters. Update the index function and memory analysis.
- Compare a trie to sorting a word array and binary-searching prefixes. Which workload makes each design attractive?
🎯 Key Takeaways
- ✓A trie stores shared prefixes as shared paths in a rooted tree.
- ✓A terminal marker distinguishes a complete word from a prefix.
- ✓Insert and lookup take O(L) time for input length L under fixed-array child access.
- ✓Alphabet design affects validation, lookup, and memory per node.
- ✓Autocomplete cost includes enumerating and returning the results.
- ✓Use the Interview Problem-Solving Patterns unit for separate interview-oriented practice.
Next
Track connected components efficiently as undirected edges are added.
HELP US IMPROVE
How was this lesson?
Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.
Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.
Discussion
0Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.
