Skip to content
Back to Data StructuresAll lessons

Data Structures

Trie

Insert or search a word with L letters: O(L). You only take as many steps as the word is long, no matter how many other words you store.

The idea, in plain English

A trie (say 'try', short for retrieval tree) is like a filing cabinet organized one letter at a time. Each drawer holds a single letter. Opening a drawer reveals more drawers for the next letter. Words that share a beginning also share the same drawers.

How it works

  1. 1Start at an empty root — no letters yet.
  2. 2For each letter in a word, step into (or create) the drawer for that letter.
  3. 3Mark the drawer for the word's last letter as 'a complete word ends here.'
  4. 4To check a word or prefix, walk the same drawers letter by letter.

When you'd use it

Use a trie for autocomplete and search suggestions, spell checkers, or anything that must quickly find all words starting with a given prefix.

Common beginner mistakes

  • Don't confuse 'this is a prefix of a stored word' with 'this exact word was stored.' 'Cat' can be part of the path to 'catalog' without 'cat' itself ever being inserted.
  • Remember to mark the end of a word. If you forget, every stored prefix looks like a complete word, or none of them do.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Has 'car': yes
Has 'ca': no
Starts with 'ca': yes
Starts with 'dog': no

See it in motion

Watch it file lettersTrie (prefix tree)Insert or search a word with L letters: O(L). You only take as many steps as the word is long, no matter how many other words you store.
•

Empty root — no letters yet. Insert words letter by letter.

0
Words
1
Nodes
1/19
Step
0.0s
Time
Current letterOn the pathNew / word-endFiled

Not sure this is the right topic? See the learning paths → or where this leads →