Trie Algorithm for Efficient Autocomplete

Type "pro" into a search bar and get suggestions like "programming", "product", "project." That's autocomplete. Behind it, there's often a Trie.

A Trie (pronounced "try") is a tree where each node represents one character. Paths from root to leaf spell out words. Nodes that share a common prefix share the same path. That shared structure is what makes prefix lookups fast.

How it works

Insert a word letter by letter, creating child nodes as needed. Mark the end of complete words. To autocomplete, walk down the Trie following the prefix, then collect all words below that point.

class TrieNode {
    children: Map<string, TrieNode>;
    isEndOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
    }
}

class Trie {
    root: TrieNode;

    constructor() {
        this.root = new TrieNode();
    }

    insert(word: string): void {
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new TrieNode());
            }
            current = current.children.get(char)!;
        }
        current.isEndOfWord = true;
    }

    autocomplete(prefix: string): string[] {
        let current = this.root;
        for (const char of prefix) {
            if (!current.children.has(char)) return [];
            current = current.children.get(char)!;
        }
        return this.collectWords(current, prefix);
    }

    private collectWords(node: TrieNode, prefix: string): string[] {
        const results: string[] = [];
        if (node.isEndOfWord) results.push(prefix);

        for (const [char, child] of node.children) {
            results.push(...this.collectWords(child, prefix + char));
        }
        return results;
    }
}

Complexity

• Insert: O(m) where m is the word length.
• Autocomplete: O(p + k) where p is the prefix length and k is the total characters in all matching words.
• Space: O(n * m) where n is the number of words and m is the average length. Worst case, no prefixes are shared and every character gets its own node.

The trade-off

Tries use more memory than a sorted array with binary search. Each node has a Map of children — that's a lot of overhead for small datasets. For 100 words, a filtered array is simpler and fast enough. For 100,000 words with common prefixes, a Trie pays for itself.

In production, you'd also consider a compressed Trie (radix tree) that merges single-child chains into one node, cutting memory significantly.