Trie (Prefix Count) Algorithm Tutorial

Trie (Prefix Tree)

A Trie, also known as a prefix tree or digital tree, stores strings so that all strings with a common prefix share the same path from the root. This makes prefix queries run in $O(L)$ time where $L$ is the prefix length.

Each node contains an array of children (one per character) and a count of how many words pass through that node.

class TrieNode:
    children = array of size 26, initialized to null
    prefixCount = 0

function insert(root, word):
    node = root
    for each char c in word:
        index = c - 'a'
        if node.children[index] is null:
            node.children[index] = new TrieNode()
        node = node.children[index]
        node.prefixCount = node.prefixCount + 1

function countPrefix(root, prefix):
    node = root
    for each char c in prefix:
        index = c - 'a'
        if node.children[index] is null:
            return 0
        node = node.children[index]
    return node.prefixCount

How prefixCount works: Every time you insert a word, you increment the count at each node along the path. The count tells you how many inserted words pass through that node.

Memory optimization: For sparse tries with many possible characters, you use a hash map instead of a fixed-size array for children.

Applications: You use Tries for autocomplete, spell checkers, IP routing tables, and word games like Boggle.

Time complexity: $O(L)$ per operation where $L$ is the string length.

Space complexity: $O(T)$ where $T$ is the total length of all inserted strings.