Tries

A trie is a variant of a $n$-ary tree where characters are stored at each node, and each path down the tree can represent a word:

The $*$ nodes represent the fact that all letters leading up to that node in the trie form a valid word-- for example, in this case, MANY is a valid word.

In interview questions, tries are very often used to store the entire English language for quick prefix lookups. A hash table can do quick lookups to tell us if a word is valid in a certain language, but not for prefixes of a word-- a trie can do this well.

A trie can lookup if a string is a valid word of prefix in $O(k)$ time, where $k$ is the length of the string (this is the same performance as a hash table, since although lookup is constant time in a hash table, reading all the characters of a string is $O(k)$).

Remember tries for problems involving lists of valid words.