Tries

A tree specialized for prefix operations over strings — each edge is a character, each path from the root is a prefix.

Study first: Trees

What it is

A trie (prefix tree) stores strings by sharing common prefixes: each node represents one character position, and a path from the root spells out a prefix. A boolean flag on a node marks "a complete word ends here."

Core operations

Insert — walk from the root, creating child nodes for characters not yet present, O(L) for a word of length L.
Search / startsWith — walk the same path; search also checks the end-of-word flag, startsWith doesn't need to.

Why not just a hash set of strings?

A hash set gives O(1) exact-match lookup but can't answer "does any word start with this prefix?" without scanning every entry. A trie answers that in O(L) — the length of the prefix, independent of how many words are stored.

Where it shows up

Autocomplete, spell-checkers, and IP-routing (longest-prefix match) all lean on the same "shared prefix" structure.