A prefix can represent many intentions
Suppose a learner types gr in the CodeBhavya search box. The system should quickly return terms such as graph and greedy. A useful result is not merely alphabetical: frequently selected terms should appear first, while equal-frequency terms need a deterministic tie-break.
The dictionary changes over time. Administrators can add or remove terms, and each selection raises that word’s popularity score. The system therefore needs efficient prefix navigation, shared storage and safe updates.
Query
Locate the node represented by the typed prefix.
Explore
Enumerate complete words below that node.
Rank
Prefer higher frequency, then alphabetical order.
Translate the product idea into contracts
| Operation | Input | Required result |
|---|---|---|
| Add term | Alphabetic word | Create only missing prefix nodes and mark its final node |
| Suggest | Valid prefix | Return at most five best matching words |
| Record selection | Existing complete word | Increase only that word’s frequency |
| Remove | Existing complete word | Unmark it and prune nodes that no other word requires |
| Exit | None | Release every allocated Trie node |
Boundary cases
- A query whose path does not exist must return no suggestions.
- A prefix may itself be a stored word, such as
artbeforearticle. - Deleting
triemust not delete a shared prefix required bytrigger. - Repeated insertion must update the terminal score without duplicating the word.
- Uppercase input is normalised; digits and punctuation are rejected by this version.
Why a Trie matches prefix search
TrieNode = { child[26], isWord, frequency }
root → g → r → a → p → h*
↘ e → e → d → y*Each edge represents a character. Words with the same beginning share the same path, so the prefix is processed once. After reaching the prefix node, depth-first traversal discovers only words inside that prefix subtree.
| Candidate | Prefix lookup | Update | Trade-off |
|---|---|---|---|
| Unsorted array | O(nL) | Simple append | Every query scans every word |
| Sorted array | O(L log n) search | Costly movement | Compact and cache-friendly |
| Hash table | Not naturally supported | Expected O(L) | Strong for exact lookup |
| Trie | O(P) to prefix node | O(L) | Chosen; faster prefixes but many pointers |
Here, L is word length and P is prefix length. Collecting matches still costs time proportional to the explored subtree; a Trie does not make result generation free.
Rules that keep the dictionary trustworthy
- Every child index is derived from a lowercase letter:
word[i] - 'a'lies from 0 through 25. - A path can exist without representing a word; only
isWord == 1makes it a valid result. - A frequency belongs to the terminal node of exactly one complete word.
- Deletion may free a node only when it is non-terminal and has no children.
- The root is never removed by a word-deletion operation.
- Every node reachable from root is released exactly once during final cleanup.
Search is navigation followed by controlled exploration
Autocomplete pipeline
- Normalise and validate the prefix.
- Follow one child pointer per character. Stop if any required pointer is NULL.
- Copy the prefix into a working buffer.
- Run DFS from the prefix node. Whenever
isWordis true, save the buffer and frequency. - Sort collected candidates by descending frequency and then ascending word.
- Display the first five entries.
Recursive deletion
The base case unmarks the terminal node and clears its score. As recursion returns, a child reports whether it became unnecessary. Its parent frees that child and clears the pointer. The return value is therefore not “word removed”; it means “this node may now be pruned.” A separate flag records whether the requested complete word existed.
Compiler-ready C11 program
Loading source…Implementation reading order
Foundation
Start with createNode, normalization and insertion.
Query
Follow findPrefixNode, DFS collection and ranking.
Ownership
Finish with recursive deletion and freeTrie.
The fixed suggestion array keeps the example approachable. For an unbounded dictionary, use a dynamically growing vector or maintain top suggestions at each Trie node.
Trace gr and its ranked results
- Begin with prefix gr and follow character g.
- Follow character r.
- Explore the gra branch.
- Explore the gre branch.
- Finish collecting.
- Apply ranking comparator.
- Return up to five results.
Press Next to begin.
Test shared paths, ranking and invalid input
Test 1 — Existing prefix
gr. The sample data must return graph before greedy because 22 is greater than 11.Test 2 — Ranking update
Test 3 — Prefix is a word
Test 4 — Safe deletion
Test 5 — Rejection and cleanup
State the cost with the missing variables included
| Operation | Time | Extra space | Explanation |
|---|---|---|---|
| Insert / exact navigation | O(L) | O(L) new nodes worst case | One edge per character |
| Reach prefix node | O(P) | O(1) | Follow prefix path |
| Collect matches | O(S) | O(H + R) | Explore S subtree nodes; recursion height H; R results |
| Rank R matches | O(R log R) | Depends on sort | Comparison sorting |
| Delete word | O(L · A) | O(L) | Current hasChildren scans alphabet A=26 at return steps |
A direct child array makes transitions O(1) but consumes 26 pointers in every node. A sparse map of children saves memory when branching is low, at the cost of slower or more complex access.
Check the reasoning
The path c-o-d-e exists. What proves that “code” is a valid result?
When must recursive deletion stop pruning?
Extension challenges
- Support phrases containing spaces while preserving safe character indexing.
- Use a size-five min-heap so ranking does not sort every candidate.
- Store the top five descendants at each Trie node and explain update costs.
- Add edit-distance suggestions for one-character typing errors.
- Persist the dictionary and scores in a file between sessions.
Explain the trade-offs, not just the code
Why can a Trie be faster than scanning all strings?
It navigates directly to the prefix node in O(P). Only that node’s descendants can match, so unrelated dictionary regions are skipped.
Why is autocomplete not simply O(P)?
O(P) reaches the prefix node. Producing suggestions additionally explores matching descendants and may rank many results. Output-sensitive work must be included.
How can memory usage be reduced?
Replace the 26-pointer array with a compact child list or map, compress single-child chains into radix edges, or use a ternary search tree.
How would a large service avoid sorting every query?
Cache a small ranked candidate list at each prefix node. Reads become fast, while insertions and popularity updates must repair caches along the word’s path.
Is popularity alone a sufficient ranking signal?
No. A real system may combine global popularity, recency, spelling quality, context and user preferences, with privacy and fairness constraints.
Fast navigation and useful ranking are separate concerns
The Trie narrows the search space by structure; it does not decide which match is best. A complete design separates prefix retrieval, candidate collection, ranking policy and memory ownership so each can be tested independently.