A trie is a tree where each path from the root spells a stored word. The children map is what makes prefix lookup O(prefix.length): we walk one node per character without scanning siblings. Storing the original word at the terminal (rather than reconstructing it from the path) saves us a string-build on every result; for 50 suggestions in the dropdown that is the difference between 4ms and 12ms. Normalizing to lowercase on both insert and lookup is what makes "apple" and "Apple" match without a separate case-folding index.

The frequency-weighted variant is what we actually shipped. collectFrom walks the subtree under the prefix node; even for a popular prefix like "a" the subtree size is bounded by the number of words sharing that prefix, which on our 80k-product index is at most a few thousand and finishes in well under a millisecond. Sorting the collected pairs and slicing the top K is fine at this scale; if you have millions of words per prefix you switch to a heap or store top-K on every internal node. Storing freq at the terminal (not at every internal node) is the simple version, and it has been good enough for every project I have shipped.

Fuzzy matching is where most teams reach for a Levenshtein library and pay 50ms per query. With maxEdits = 1 the search is still bounded: each query character either matches a child exactly (no edit) or branches into at most |alphabet| substitutions and one skip, giving roughly |prefix| * (|alphabet| + 1) work. For our product names with 27 effective chars and prefixes around 5, that is well under a millisecond. The seen dedup at the end is necessary because a substitution path and a skip path can converge on the same word at different edit counts, and we want the lower one.