# Trie sorting based on word frequency

Given a trie with word occurrences (frequency), how can we sort the words( both ascending and descending) on the basis of their frequency?

• Is there any relation between the trie and frequencies? Do you create the trie yourself from given words? – fade2black Aug 7 '17 at 9:35
• I think it's quite clear that a basic trie doesn't help with this task at all. Create a list or array and sort that one using standard algorithms. If you want a data structure that combines be benefits of tries as set representation and quick output of a frequency-sorted list, you'll have to do something else. – Raphael Aug 7 '17 at 9:52

As the comments say, the basic trie will not help with this task. So I'll propose a special trie for this task. It is the same in every way to normal trie except the "end-of-word" (EOW) nodes (Note that these are not necessarily leaf nodes as words may overlap, e.g. "the" and "theory").

Forget the trie for a moment and imagine all words of frequency 1 in a linked list. Now imagine we have multiple linked lists for each frequency. Now we have $k$ linked lists if there are $k$ distinct frequencies. We can chain these links together, in order of frequency, to create a linked list of linked lists. You could imagine something like this:

We will try to add this same idea into the EOW nodes in the trie without messing up the trie structure. It will be similar, but we will also need every EOW node to point to the sentinel node of their respective frequency list. We will have the following properties in the EOW nodes:

• head - head (or sentinel) of this frequency list.
• next - next EOW node in this frequency list.
• prev - previous EOW node in this frequency list.
• frequency - frequency of the word that ends at this EOW node.

The sentinel node will also have a next_head and prev_head field to go to the next and previous frequency list. Similarly the empty root of our trie will act as a sentinel to the first frequency list (i.e. root.next_head is frequency_list_1.head). It will look something like this:

Now we just need to modify the insertion procedure a little bit to accommodate these changes. Specifically the changes will occur when we reach the EOW node. I had started writing the changes out in pseudocode but it became a bit cumbersome. So there are probably easier ways to do this. The idea still is the same. Insertions should only increase by $O(1)$ operations because you'll never have to move a node more than one frequency list at a time, and if you have the necessary pointers this is fine. From there it's as simple as iterating over the list of lists of EOW nodes.

### Analysis:

Let the words be a set $S$ of $n$ words and $k$ unique words (apologies for reusing $k$, this is different than the first $k$ we define).

Then we have that the insertion time for all words will be $O(sum\{|S_i|\})$. Or if we say $m$ is the length of the longest word, then it is $O(m \cdot n)$. Then after insertions getting the frequencies in order is $O(k)$ and $O(n)$ for the simple traversal.