I was wondering how can you change the behavior of Trie data structure to support auto completion by popularity of certain words for example?
I was thinking about each node holds a linked list that is sorted by the popularity, is that a good idea? but then how can you know the order of the words the auto complete will show?
first, you have to add an attribute popularity to the trie node, and always a node is chosen, you increase it's popularity by 1.
then, let's suppose you wanna get the suggestions between all words starting with "abc".
first, you walk normally in the trie until you reach the node that represents "abc", then you can call a In-Order tree traversal starting is that node, and always you visit a node, you add it in a priority_queue (or heap), which will sort the nodes just as you define it to. You can define it to sort the nodes as the greatest popularity will be the priority.
after the traversal is done, you can remove the elements from the heap one by one (as many as you want) and each element you remove will be the greatest between all elements left (the first element will be the greatest of all, the second will be the greatest between all elements left, etc.)
You can read this if you are interested in time and space complexity:
this approach takes time O(size of word) to find the root node, then O(n lg n) to sort the nodes you want and then O(k lg n) to get the first k elements you need to show. In a nutshell, the time complexity is O(n lg n) and the space complexity is O(n) because of the heap.