The Trie I Built for Search-Bar Autocomplete

// A trie node holds a children map and a 'terminal' flag plus the original
// word at the terminal. We store the word at terminals so prefix-walk can
// emit results without reconstructing them character by character.

class TrieNode {
    constructor() {
        this.children = new Map();
        this.word = null;
    }
}

function makeTrie() {
    const root = new TrieNode();

    function normalize(s) {
        return s.toLowerCase();
    }

    function insert(word) {
        let node = root;
        for (const ch of normalize(word)) {
            let next = node.children.get(ch);
            if (!next) {
                next = new TrieNode();
                node.children.set(ch, next);
            }
            node = next;
        }
        node.word = word;  // store the original casing
    }

    function findPrefix(prefix) {
        let node = root;
        for (const ch of normalize(prefix)) {
            const next = node.children.get(ch);
            if (!next) return null;
            node = next;
        }
        return node;
    }

    return { insert, findPrefix };
}

const trie = makeTrie();
for (const w of ['Apple', 'Application', 'Apply', 'Apricot', 'Banana', 'Band', 'Bandage']) {
    trie.insert(w);
}

console.log('node for "app":', trie.findPrefix('app') ? 'found' : 'missing');
console.log('node for "ban":', trie.findPrefix('ban') ? 'found' : 'missing');
console.log('node for "xyz":', trie.findPrefix('xyz') ? 'found' : 'missing');

// Real autocomplete ranks suggestions: 'iphone' should come before 'ipo'
// for the prefix 'ip'. We track a per-word frequency, store it on the
// terminal, and during prefix-walk collect (word, freq) pairs then return
// the top K by frequency.

class TrieNode {
    constructor() {
        this.children = new Map();
        this.word = null;
        this.freq = 0;
    }
}

function makeAutocomplete() {
    const root = new TrieNode();
    const norm = (s) => s.toLowerCase();

    function insert(word, freq = 1) {
        let node = root;
        for (const ch of norm(word)) {
            let next = node.children.get(ch);
            if (!next) { next = new TrieNode(); node.children.set(ch, next); }
            node = next;
        }
        node.word = word;
        node.freq += freq;
    }

    function collectFrom(node, out) {
        if (node.word) out.push({ word: node.word, freq: node.freq });
        for (const child of node.children.values()) collectFrom(child, out);
    }

    function suggest(prefix, k = 5) {
        let node = root;
        for (const ch of norm(prefix)) {
            const next = node.children.get(ch);
            if (!next) return [];
            node = next;
        }
        const out = [];
        collectFrom(node, out);
        out.sort((a, b) => b.freq - a.freq);
        return out.slice(0, k);
    }

    return { insert, suggest };
}

const ac = makeAutocomplete();
const seed = [
    ['iphone', 9000], ['ipad', 2000], ['ipod', 200], ['ipo', 800],
    ['ip address', 500], ['iphone case', 4000], ['iphone charger', 1200],
];
for (const [w, f] of seed) ac.insert(w, f);

console.log('suggest("ip"):  ', ac.suggest('ip', 3));
console.log('suggest("ipho"):', ac.suggest('ipho', 3));
console.log('suggest("x"):   ', ac.suggest('x', 3));

// Users mistype the first character. 'aplple' and 'apple' should match.
// Add a one-edit tolerance: at each step, optionally skip a character in
// the query (insertion in the input) or substitute (any child counts).
// We cap edits at 1 to keep the search bounded.

class TrieNode {
    constructor() { this.children = new Map(); this.word = null; this.freq = 0; }
}

function insert(root, word, freq = 1) {
    let node = root;
    for (const ch of word.toLowerCase()) {
        let next = node.children.get(ch);
        if (!next) { next = new TrieNode(); node.children.set(ch, next); }
        node = next;
    }
    node.word = word; node.freq += freq;
}

function fuzzyMatch(root, query, maxEdits = 1, k = 5) {
    const lower = query.toLowerCase();
    const out = [];

    function walk(node, i, edits) {
        if (node.word && i >= lower.length - 1) {
            out.push({ word: node.word, freq: node.freq, edits });
        }
        if (i >= lower.length) return;
        const ch = lower[i];
        const exact = node.children.get(ch);
        if (exact) walk(exact, i + 1, edits);
        if (edits < maxEdits) {
            // Substitute: try each other child as if the query char were that char.
            for (const [c, child] of node.children) {
                if (c !== ch) walk(child, i + 1, edits + 1);
            }
            // Skip a query char (typo where user added an extra letter).
            walk(node, i + 1, edits + 1);
        }
    }

    walk(root, 0, 0);
    out.sort((a, b) => a.edits - b.edits || b.freq - a.freq);
    const seen = new Set();
    const dedup = [];
    for (const r of out) {
        if (!seen.has(r.word)) { seen.add(r.word); dedup.push(r); }
        if (dedup.length >= k) break;
    }
    return dedup;
}

const root = new TrieNode();
for (const [w, f] of [['apple', 9000], ['apply', 1000], ['april', 500], ['banana', 2000]]) {
    insert(root, w, f);
}

console.log('aplple ->', fuzzyMatch(root, 'aplple'));   // matches apple at edits=1
console.log('appl   ->', fuzzyMatch(root, 'appl'));     // matches apple/apply at edits=0
console.log('banan  ->', fuzzyMatch(root, 'banan'));    // matches banana at edits=0