← Index

Trees & Heaps

Trie (Prefix Tree)

A tree built for strings — shared prefixes, fast prefix search.

What it is

A trie stores strings character by character down a tree, where words sharing a prefix share the same path. Searching for a word or checking if any word starts with a given prefix only costs the length of the string you're checking, O(k) — completely independent of how many words are stored.

Real-world examples

• A phone keypad predictive text system — each key press narrows down the branch of possible words, sharing the common prefix already typed.
• A dictionary organized so that all words starting with 'app' live in the same neighborhood — 'apple', 'app', 'application' all share that path.

Where you've probably used this already

• Autocomplete/typeahead search boxes — 'give me every word starting with this prefix' is exactly what a trie is built for.
• IDE autocomplete for variable/function names as you type.
• Spell-checkers and word-game solvers (Boggle/Scrabble helpers) that need fast prefix pruning.

Complexity

Code

class TrieNode {
    constructor() {
        this.children = new Map(); // Stores child characters
        this.isEndOfWord = false;  // Marks the end of a complete word
    }
}

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

    // 1. Insert a word into the Trie
    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char);
        }
        node.isEndOfWord = true;
    }

    // 2. Search for a complete word in the Trie
    search(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                return false; // Character path doesn't exist
            }
            node = node.children.get(char);
        }
        return node.isEndOfWord; // Return true only if it's the end of a full word
    }

    // 3. Check if any word starts with a given prefix
    startsWith(prefix) {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children.has(char)) {
                return false; // Prefix path doesn't exist
            }
            node = node.children.get(char);
        }
        return true;
    }
}

// --- Example Usage ---
const trie = new Trie();

// Insert words
trie.insert("apple");
trie.insert("app");
trie.insert("bat");

// Search for words
console.log(trie.search("apple")); // true
console.log(trie.search("app"));   // true
console.log(trie.search("bat"));   // true
console.log(trie.search("apps"));  // false (never inserted)

// Check prefixes
console.log(trie.startsWith("app"));  // true
console.log(trie.startsWith("bat"));  // true
console.log(trie.startsWith("ban"));  // false