Search Suggestions System

Every output list must be lexicographic, so sorting the products up front removes ordering from the rest of the problem entirely.

Trie version: insert the sorted products, walk to the node for each prefix, and DFS from it visiting children in sorted character order, stopping after three completions. Because children are visited in order, the first three found are the three smallest - no sorting per query. Each prefix walk continues from the previous node, so the whole search word costs one pass.

Sorted-scan version: after sorting, all products sharing a prefix are contiguous. Binary search the first product `>= prefix` and take up to three consecutive entries that still start with it. Fewer moving parts, and interviewers generally accept it, but say why it works: contiguity is a consequence of the sort, not an assumption.

One detail worth handling deliberately: once a prefix matches nothing, no longer prefix can match either, so the remaining answers are all empty - the `"tatiana"` case, where the trie walk falls off at the first character and everything after is `[]`.