• 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 (sometimes called “null nodes”) are often used to indicate complete words.
  • Actual implementaton of * nodes might be a speacial type of child (such as TerminatingTrieNode, which inherits from TrieNode). Or, we could use just a boolean flag terminates within the “parent” node.
  • Very commonly used, a trie is used to store the entire (English) language for quick prefix lookups.