DSA · interactive
Trie: prefix lookups
A trie stores words letter by letter, sharing common beginnings. To find every word that starts with a prefix, walk one node per letter, then collect everything below. The cost depends on the prefix length, not on how many words there are.
7 words · 10 nodes · ● marks the end of a word
- c
- a
- r● car
- d● card
- e● care
- t● cat
- r● car
- a
- d
- o● do
- g● dog
- t● dot
- o● do
“car” → car, card, care
3 steps down the tree, then collect the 3 words below.
Type a prefix
1 2 Follow one child per letter. If a child is missing, no word starts that way: stop early.
O(length of prefix).
3 4
In production
Tools and technologies
Tries power prefix search in many systems.
Not tied to one language — use these names when you search docs or design a system.