Trie (prefix tree)

O(len) per op

Store words in a tree where each node holds one character and the path from the root spells a prefix. Words sharing a beginning share the same nodes, so insert/search/prefix checks cost only the length of the word.

Signals

autocomplete or typeahead over many stringslongest common prefix among wordsinsert, search, and starts-with on a word setmatch against a large fixed dictionary by prefix

Template

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEnd = false;
    }
}
class Trie {
    constructor() { this.root = new TrieNode(); }
    insert(word) {
        let node = this.root;
        for (const c of word) {
            if (!node.children.has(c)) node.children.set(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEnd = true;
    }
    search(word) {
        let node = this.root;
        for (const c of word) {
            if (!node.children.has(c)) return false;
            node = node.children.get(c);
        }
        return node.isEnd;
    }
}

Looks similar, isn't

Hash set / map: A hash set or map answers exact-key membership in O(1) but has no notion of one string being a prefix of another. A trie shares the storage for common prefixes and walks character by character, which is what lets it answer autocomplete and longest-prefix questions that a hash map cannot.

up to 1e5 words of length up to L, one walk per character -> O(len) per insert/search/prefix check, independent of how many other words are stored.

Learn this pattern