Tries

What is a trie?

A trie is a data structure that allows storing sets of strings. Tries let you:

• Store strings made up of any elements
• Perform lookup, insertion, and deletion in O(L) where L is the length of the string
• Store the strings as a set (i.e. elements must be unique)

How do tries work?

Observe the following diagram containing "do", "dog", "dot", "doting", "drag", "drastic", "to", "top", "torn", and "trap". Note that the data is stored in the edges, not the nodes:

For more information on tries, see here

Image credit