A trie stores strings by prefixes: each node represents a character. It enables fast prefix search/autocomplete; lookup is O(L), where L is the word length.
A trie (prefix tree) stores keys character-by-character. Each node is a prefix, and a terminal marker indicates a full word. Operations depend on key length L, not on the number of stored keys (aside from memory and cache effects).
Typical operations:
type Node = { end: boolean; next: Map<string, Node> }
const root: Node = { end: false, next: new Map() }
function insert(word: string) {
let node = root
for (const ch of word) {
const child = node.next.get(ch) ?? { end: false, next: new Map() }
node.next.set(ch, child)
node = child
}
node.end = true
}
function startsWith(prefix: string): boolean {
let node = root
for (const ch of prefix) {
const child = node.next.get(ch)
if (!child) return false
node = child
}
return true
}