Tries

A trie (prefix tree) stores strings character by character along tree edges, so words sharing a prefix share the same path. It turns "does any word start with this prefix?" into a walk proportional to the prefix length instead of a scan of every word.

Key concepts

• Each node holds children keyed by character, plus a flag marking "a word ends here."
• Inserting and searching both walk one character at a time from the root.
• Prefix search stops as soon as the path breaks — no need to check whole words.

When to use it

• You're repeatedly checking prefixes (autocomplete, spell-check, word search on a grid).
• You need to store a large dictionary of words and query it efficiently by prefix.

Tips

• A map from character to child node (or a fixed-size array for lowercase-only alphabets) per node is the simplest implementation.
• Combine a trie with DFS/backtracking for grid-based word search problems — it prunes paths early.
• Don't forget the "end of word" marker — without it, you can't tell a valid word from just a valid prefix.

Practice problems (3)

Blind 75 (3):

• Implement Trie Prefix Tree Medium — Read & practice · LeetCode ↗
• Design Add And Search Words Data Structure Medium — Read & practice · LeetCode ↗
• Word Search II Hard — Read & practice · LeetCode ↗