Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A trie (prefix tree) is a tree keyed by characters rather than whole keys
A trie (prefix tree) is a tree keyed by characters rather than whole keys.
Each node stores one character, and a word is a path from the root to a node marked as the end of a word.
Shared prefixes are stored once, which makes prefix operations (autocomplete, spell checking) extremely fast — proportional to word length, not dataset size.
How It Works
The root represents the empty string.
Inserting a word walks existing edges character by character, creating nodes only for missing characters, then marks the final node with an end-of-word flag.
Searching a word either fails on a missing edge or succeeds if the final node is marked.
A prefix query walks the prefix and then enumerates the subtree below it.
Lookup and insertion are both O(m) where m is the word length, independent of how many words are stored, at the cost of O(Σ·n·m) worst-case space.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Insert word (length m) | O(m) | O(m) |
| Search word | O(m) | O(1) |
| Prefix query | O(m) | O(1) |
| Autocomplete enumeration | O(m + k) | O(k) |
| Space | O(Σ · n · m) worst-case | O(Σ · n · m) worst-case |
Best Use Cases
- Autocomplete and type-ahead suggestions
- Spell checking and word dictionaries
- IP routing (longest-prefix match in routers)
- Predictive text and T9 phone input
- Word frequency counting and boggle-style puzzles
Worked Example
Insert [bat, ball, bath, cap, cat, car], then search ball and prefix ba
Input: words: bat, ball, bath, cap, cat, car; search "ball"; prefix "ba"- 1 Insert bat: create nodes b → a → t, marking the t node as an end of word.
- 2 Insert ball and bath: they share the b → a prefix, branching at t (ball, bath) vs t (bat).
- 3 Insert cap, cat, car: a second subtree rooted at c → a with branches p, t, r.
- 4 Search "ball": walk b → a → l → l; the final node is marked as a word — found.
- 5 Prefix query "ba": walk b → a, then enumerate the subtree — bat, ball, bath all start with "ba".
- 6 Each operation costs O(m) where m is the word length, independent of the dictionary size.
Pseudocode
function insert(root, word):
cur = root
for ch in word:
if ch not in cur.children:
cur.children[ch] = new Node(ch)
cur = cur.children[ch]
cur.isEnd = true function search(root, word):
cur = root
for ch in word:
if ch not in cur.children:
return false
cur = cur.children[ch]
return cur.isEnd function startsWith(root, prefix):
cur = root
for ch in prefix:
if ch not in cur.children:
return false
cur = cur.children[ch]
return collectWords(cur, prefix)
function collectWords(node, acc):
results = []
if node.isEnd: results.add(acc)
for ch, child in node.children:
results += collectWords(child, acc + ch)
return results Insert Words
Each node stores one character; words are paths from the root that share prefixes.