Tries

If hash maps are about looking up exact values, tries are about looking up prefixes. They're the data structure behind autocomplete, spell checkers, and any problem that cares about what a string starts with.

This post breaks down what tries are, how they work under the hood, and why their performance characteristics make them irreplaceable for prefix-based problems.

What is a trie?

A trie (pronounced "try") is a tree where each path from root to node represents a prefix of some string. The root is empty. Each edge represents a character.

Some everyday examples:

• Your phone's autocomplete — type "hel" and it suggests "hello", "help", "helmet"

• Spell checkers — is this sequence of characters a real word?

• Search engines — suggest queries as you type

• IP routing tables — longest prefix matching

The name comes from retrieval. It's a tree optimized for retrieving strings by their prefixes.

A trie is a tree of characters

Under the hood, a trie is a tree where:

• The root is an empty node
• Each node has a dictionary of children: children[char] → TrieNode
• Each path from root to a node spells out a prefix
• Some nodes are marked as end-of-word — meaning a complete string ends here

The key insight: strings that share a prefix share nodes. "cat" and "car" share the c → a path. This is what makes tries space-efficient for dictionaries with overlapping prefixes.

Insert is O(m)

Inserting a word of length m means walking m levels down the tree, creating nodes as needed, and marking the last node as end-of-word.

No hashing, no collisions. Each character takes you one level deeper. Total work: O(m) where m is the word length.

Search is O(m)

To check if a word exists, follow the path character by character. If you reach the end and the node is marked as end-of-word, the word exists.

This is also O(m). Compare that to a hash map lookup which is O(m) too (because hashing the string takes O(m)). The trie matches hash map speed for exact lookups — but can do things hash maps can't.

Prefix query is O(m) — and this is where tries shine

Checking "does any word start with this prefix?" is the same as search, but you don't need the end-of-word check. If you can follow the path, the prefix exists.

A hash map cannot do this efficiently. To check if any key starts with "hel", you'd have to scan every key. A trie does it in O(m).

This is the reason tries exist.

Delete is O(m)

To delete a word, unmark its end-of-word flag. Optionally, clean up nodes that are no longer part of any word (no children, not end-of-word).

In practice, most interview problems only need insert, search, and starts_with. Delete is rare.

There is no random access

You cannot "get the 5th word" from a trie. Tries are not ordered by insertion time — they're ordered by lexicographic structure.

If you need all words in sorted order, a DFS traversal gives them to you for free (tries store strings in sorted order by nature).

Memory usage is the tradeoff

Each node has a dictionary of children. For a trie storing English words, each node could have up to 26 children. In practice, most nodes are sparse.

For interview problems, memory is rarely the bottleneck. But in production, if you're storing millions of strings, a compressed trie (radix tree) or a hash map might be more practical.

When a problem is secretly about tries

"Find all words that start with..." — if the problem involves prefix matching across a dictionary, that's a trie.

"Word search on a board" — Word Search II on LeetCode. Build a trie of dictionary words, then DFS the grid. The trie lets you prune branches where no dictionary word could possibly match.

"Longest common prefix" — insert all strings into a trie, then walk down the single-child path from the root.

"Autocomplete / type-ahead" — classic trie application. Walk to the prefix node, then collect all words below it.

"Count words with a given prefix" — store a count at each node that tracks how many words pass through it.

The full implementation

Know the common trie operations

For the implementation above:

• trie.insert(word) → O(m)
• trie.search(word) → O(m)
• trie.starts_with(prefix) → O(m)

Where m is the length of the word or prefix. No operation depends on how many words are in the trie — only on the length of the query.

Final takeaway

Tries are the answer when hash maps aren't enough.

Understanding:

• that a trie is a tree of characters, where shared prefixes share nodes
• that insert, search, and prefix queries are all O(m)
• that the killer feature is prefix lookup — something hash maps can't do efficiently
• the interview cues: "prefix", "starts with", "autocomplete", "word search"

will let you recognize trie problems instantly and implement them cleanly.