Tries

// 1) Basic implementation — array-of-children variant for tiny alphabets
class TrieNode {
    constructor() {
        this.children = new Map();   // char -> TrieNode (or Array for ASCII only)
        this.isEnd    = false;        // marks the end of an inserted word
        this.count    = 0;            // number of words passing through this node
    }
}

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

    insert(word) {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
            node = node.children.get(ch);
            node.count++;
        }
        node.isEnd = true;
    }

    contains(word) {
        const node = this._find(word);
        return !!node && node.isEnd;
    }

    startsWith(prefix) {
        return this._find(prefix) !== null;
    }

    _find(s) {
        let node = this.root;
        for (const ch of s) {
            node = node.children.get(ch);
            if (!node) return null;
        }
        return node;
    }
}

// 2) Use it
const trie = new Trie();
['apple', 'app', 'application', 'apt', 'art'].forEach((w) => trie.insert(w));
trie.contains('app');         // true
trie.contains('ap');          // false  — 'ap' is a prefix, not an inserted word
trie.startsWith('app');       // true

// 3) Autocomplete — collect all words with a prefix
function wordsWithPrefix(trie, prefix) {
    const node = trie._find(prefix);
    if (!node) return [];
    const out = [];
    (function dfs(n, current) {
        if (n.isEnd) out.push(current);
        for (const [ch, child] of n.children) dfs(child, current + ch);
    })(node, prefix);
    return out;
}

wordsWithPrefix(trie, 'app');     // ['app', 'apple', 'application']

// 4) Top-K autocomplete with frequency counts
class FreqTrie {
    constructor() { this.root = new TrieNode(); }
    insert(word, freq = 1) {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
        node.freq  = (node.freq ?? 0) + freq;
    }
    topK(prefix, k = 5) {
        const start = this._find(prefix);
        if (!start) return [];
        const results = [];
        (function dfs(n, cur) {
            if (n.isEnd) results.push({ word: cur, freq: n.freq });
            for (const [ch, child] of n.children) dfs(child, cur + ch);
        })(start, prefix);
        return results.sort((a, b) => b.freq - a.freq).slice(0, k);
    }
    _find(s) {
        let node = this.root;
        for (const ch of s) { node = node.children.get(ch); if (!node) return null; }
        return node;
    }
}

const ac = new FreqTrie();
for (const w of ['apple', 'apple', 'app', 'application', 'apt']) ac.insert(w);
ac.topK('app', 3);    // [{word: 'apple', freq: 2}, {word: 'app', freq: 1}, ...]

// 5) Delete a word — keep the trie clean
function deleteWord(trie, word) {
    function helper(node, i) {
        if (i === word.length) {
            if (!node.isEnd) return false;
            node.isEnd = false;
            return node.children.size === 0;
        }
        const ch = word[i];
        const child = node.children.get(ch);
        if (!child) return false;
        const shouldDelete = helper(child, i + 1);
        if (shouldDelete) {
            node.children.delete(ch);
            return !node.isEnd && node.children.size === 0;
        }
        return false;
    }
    helper(trie.root, 0);
}

// 6) Word search (Leetcode 79 / 212) — trie + DFS on a grid
function findWords(board, words) {
    const trie = new Trie();
    for (const w of words) trie.insert(w);
    const R = board.length, C = board[0].length;
    const result = new Set();

    function dfs(r, c, node, path) {
        if (r < 0 || c < 0 || r >= R || c >= C) return;
        const ch = board[r][c];
        if (ch === '#') return;
        const child = node.children.get(ch);
        if (!child) return;
        const next = path + ch;
        if (child.isEnd) result.add(next);
        board[r][c] = '#';                  // mark visited
        dfs(r+1, c, child, next);
        dfs(r-1, c, child, next);
        dfs(r, c+1, child, next);
        dfs(r, c-1, child, next);
        board[r][c] = ch;                    // backtrack
    }

    for (let r = 0; r < R; r++)
        for (let c = 0; c < C; c++)
            dfs(r, c, trie.root, '');

    return [...result];
}

// 7) Radix tree (compressed trie) — each edge stores a STRING, not a single char
// Used for routing tables (IP prefix matching), DNS, web framework routers (Echo, gin).
// Insertion: walk; at a mismatch, split the edge into common prefix + two diverging children.

// 8) Persistent trie — Patricia / HAMT / immutable map
// Clojure / Scala / Immer use persistent tries to implement immutable maps with O(log32 n) ops
// (HAMT — Hash Array Mapped Trie).

// 9) Trie vs alternative data structures
//                  contains(s)       startsWith(p)    space
// Hash set         O(|s|)            no                O(N*L)
// Sorted array     O(|s| log N)      O(|p| log N)     O(N*L)
// Trie             O(|s|)             O(|p|)            O(total unique characters)
// BloomFilter      O(k)               no                very small but probabilistic
//
// Trie wins for prefix queries, autocomplete, and big shared prefixes (URLs, file paths).

// 10) Memory considerations
// • Children stored as Map — flexible, larger constant factor
// • Children stored as Array (26 slots for lowercase ASCII) — fast lookup, wasted memory if sparse
// • Pointers in JavaScript ≈ 8 bytes per child — at scale, use a typed array layout in C++/Rust
// • Compress with a radix trie when many nodes have a single child (URL paths)

// 11) Real-world uses
// • Autocomplete + spell check
// • IP routing tables — longest-prefix match
// • DNS server zone lookups
// • HTTP routers (gin, echo) — radix trees over URL paths
// • Predictive text (T9 keyboards)
// • Suffix tries / suffix arrays for substring search (advanced — Ukkonen's algorithm)
// • Genome sequence search

// 12) Persistence on disk — Marisa-trie, succinct trie
// For huge dictionaries (millions of words), libraries store tries in compact, mmappable form.
// Look for: marisa-trie (Python), datrie, libcst (Hat-trie), HAT-trie / louds-trie research.

// 13) Common bugs
// • Forgetting isEnd → prefix matches succeed but exact matches return false
// • Reusing nodes across inserts — implementation bug; each new char in a new word allocates
// • Mutating the board in word-search without backtracking — corrupts subsequent searches
// • Memory blow-up on emoji or wide Unicode — use code-point iteration, not UTF-16 code units
// • Sorting on each autocomplete query — cache top-K per prefix node if reads outpace writes
// • Treating delete as 'set isEnd = false' only — leaks unused nodes; clean up with the recursive pattern above
// • Building a trie when a hash set works — only switch when prefix queries dominate

class Trie {
    constructor() { this.root = {}; }
    insert(w) {
        let n = this.root;
        for (const c of w) n = (n[c] ??= {});
        n.end = true;
    }
    has(w) {
        let n = this.root;
        for (const c of w) { if (!n[c]) return false; n = n[c]; }
        return !!n.end;
    }
}