Prefix Search

The killer feature: "find all words starting with pre".

Time complexity:

• Walk to prefix: O(|prefix|)
• DFS: O(K) where K is total characters in matched words

For "ar*" prefix on a trie of 100k words, this is hundreds of times faster than scanning all words.

Sorted output: iterate child dict in sorted order. For ASCII a-z this is automatic if you store children in an array.

For autocomplete UIs you typically want TOP-K by frequency, not all matches. Maintain an aggregate "most-frequent word in subtree" pointer at each node for O(K) top-K.