Counting Words with Prefix

To count words with a given prefix, store counts at each node:

class TrieNode:
    children: map
    wordCount: int # words ending here
    prefixCount: int # words passing through

On insert, increment prefixCount at every node along the path, and wordCount at the final node.

def insert(word):
 node = root
 for char in word:
 if char not in node.children:
 node.children[char] = TrieNode()
 node = node.children[char]
 node.prefixCount += 1
 node.wordCount += 1

Now countWordsWithPrefix(prefix) walks to the prefix node and returns prefixCount.

This augmentation is useful for autocomplete ranking. Show completions in order of frequency.