What is a Trie?

A trie (pronounced "try", short for retrieval) is a tree-shaped data structure built for storing and searching strings by their characters. Every edge in the tree is labeled with a single character, and every path from the root down to a marked node spells one stored word.

That structure makes prefix questions extremely fast. Checking whether the trie contains any word starting with "car" is just three character lookups from the root, no matter how many thousands of words are stored. Tries are the engine behind features like autocomplete, spell-check, and IP routing tables.

Each node in the trie holds two pieces of state:

• children: a map from a character to the next TrieNode.
• isEndOfWord: a flag that is true when the path from the root to this node spells a complete word that was inserted.

The five main operations on a trie are:

1. Insert: Add a word, creating any missing nodes along the way.
2. Search: Check whether a full word is stored.
3. StartsWith: Check whether any stored word has the given prefix.
4. Delete: Remove a word and prune any dead branches.
5. WordCount: Count how many distinct words are stored.

Let's build a Trie class!