A trie stores words letter by letter along paths from the root: each edge is a letter, so the path to a node spells a prefix. Words that share a prefix share those nodes, and a double ring marks a node where a stored word ends. Looking up a word of length m takes m steps, however many words are stored.
- Typical operation
- O(m)
- Space
- O(total letters stored)