Trie

A trie stores strings in a rooted tree whose edges represent symbols; the path from the root spells a prefix. A separate terminal marker distinguishes a stored word from a prefix of another. Storing to, tea and ten shares the initial t, and tea with ten also shares te. Lookup follows one edge per symbol, taking $O(m)$ time for a length-$m$ key when child selection is constant-time. Dense child arrays use more memory than sparse maps. A trie naturally supports prefix queries and longest-prefix matching.^[ref]