A trie is a funny data structure. It comes up a lot in interview questions, but algorithm textbooks don't spend much time on this data structure. A trie is a variant of an n-ary tree in which characters are stored at each node. Each path down the tree may represent a word. The * nodes(null nodes) are often used to indicate complete words. For example, the fact that there is a * node under MANY i..
