A tree where each edge is one character, so every word sharing a prefix shares a path. Looking up a prefix costs only the length of the prefix.
Used for
c → a → t
c → a → r
2 steps
Does any stored word start with "cb"?
Not quite. Under c there is only a. With no b, no stored word starts with cb.
Step 1 of 5
Goal: store many words so we can quickly ask "does any word start with these letters?" A trie is a tree where each step down is one letter, so words that share a beginning share a path. Add "cat", starting from an empty root.
Step 2 of 5
c, a, t: each letter hangs below the previous one.
Step 3 of 5
Add "car". c and a already exist, so only r is new. Shared beginnings are stored once.
Step 4 of 5
Does anything start with "ca"? Walk c, then a. The path exists: yes, in 2 steps, however many words are stored. The cost depends on the length of the word, not the number of words. This is a trie.
Step 5 of 5
Your turn.
class Trie { root = {}; insert(w) { let n = this.root; for (const c of w) n = n[c] ??= {}; n.end = true; } startsWith(p) { let n = this.root; for (const c of p) if (!(n = n[c])) return false; return true; }}