Loading algorithms…

Loading visualizer…

Algorithms/Data Structures/Trie (Prefix Tree)

Trie (Prefix Tree)

Insert, search, and collect prefix matches character by character. The backbone of autocomplete and spell checkers.

Prefix TreeStringsAutocomplete
Stored
•
word end on active pathWords: CAT, CAR, CARE, DOG, DO, DUCK
Step 1 of 30: Start from an empty trie with just the root. Operations queued: insert("CAT"), insert("CAR"), insert("CARE"), insert("DOG"), insert("DO"), insert("DUCK"), search("CA").
1 / 30
Speed

Start from an empty trie with just the root. Operations queued: insert("CAT"), insert("CAR"), insert("CARE"), insert("DOG"), insert("DO"), insert("DUCK"), search("CA").

Operation queue

  1. insert("CAT")
  2. insert("CAR")
  3. insert("CARE")
  4. insert("DOG")
  5. insert("DO")
  6. insert("DUCK")
trie.js
1function insert(word) {
2 let node = root;
3 for (const ch of word) {
4 if (!node.children[ch])
5 node.children[ch] = newNode();
6 node = node.children[ch];
7 }
8 node.isWord = true; // mark ending
9}
10 
11function search(word) {
12 const node = walk(word);
13 return node !== null && node.isWord;
14}
15 
16function startsWith(prefix) {
17 return walk(prefix) !== null;
18}

Words build the trie first; then each queued operation walks the structure character by character

About the Trie (Prefix Tree) algorithm

Insert, search, and collect prefix matches character by character. The backbone of autocomplete and spell checkers.

Category
Data Structures
Difficulty
Easy
Time complexity
O(L) per op
Space complexity
O(A·L·n)
←Previous Algorithm
Union-Find (DSU)
Data StructuresO(α(n)) amortized
Next Algorithm→
Segment Tree
O(log n) per opData Structures