Top-K Autocomplete

Autocomplete returns the top K most-popular completions of a prefix:

Type "ja" -> [java, javascript, jacket, jam, jacuzzi]   (in popularity order)

Naive: walk all matching words, sort by frequency, return top K. O(matches log matches) per query.

Better: store frequency at each "is_word" node. At each interior node, ALSO store a sorted list (or heap) of "top K most popular words in my subtree". On insert/update, propagate up.

Query: walk to prefix node, return its top_k.

This is essentially how Google Suggest, IDE autocomplete, and YouTube's autocomplete work — the data structure is the same, the rankings are richer.