Tries (Prefix Trees)

Overview#

A variant of n-ary tree in which characters are stored at each node. Each path down the tree may represent a word.

The nodes (aka null nodes) usually indicates a complete word. Actual implementation of these nodes might be a special type of child (such as TerminatingTrieNode which inherits from TrieNode), or we can use a boolean flag terminates within the parent node.

Very commonly, a trie is used to store the entire (English) language for quick prefix lookups. While a hash table can quickly lookup whether a string is a valid word, it cannot tell us if a string is a prefix of any valid words. A trie can do this quickly.

A trie can check if a string is a valid prefix in O(K) time where K = length of string. This is actually same as runtime of hash tables. Although we refer hash table lookups as O(1), it is not entirely true as a hash must read through all the characters in input which takes O(K) time in case of a word lookup.

Many problems involving lists of valid words leverage trie as an optimization. In situations when we search through the tree on related prefixes repeatedly (eg: looking up M, then MA, then MAN, then MANY), we might pass around a reference to the current node in the tree. This allows us to just check if Y is a child of MAN, rather than starting from root each time.

Prefix Tree