Introduction to Trie (Prefix Tree)

A Trie is a tree-like data structure that is used for efficiently storing and searching strings, especially in applications like autocomplete, spell checking, and IP routing.

---

Key Properties of a Trie:

1. Nodes: Each node represents a character.
2. Root: The root node is empty and serves as the starting point.
3. Children: Each node has up to 26 children (for lowercase English letters) or more, depending on the character set.
4. End-of-Word Marker: Some nodes are marked to indicate the end of a word.

---

Basic Trie Operations:

1. Insertion

Inserting a word involves traversing the trie and creating new nodes for characters that don’t exist.

2. Search

Search checks whether a word exists in the trie by traversing its nodes.

3. Prefix Search

This checks whether any word in the trie starts with a given prefix.

---

Implementation of Basic Trie in JavaScript:

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

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

    // Insert a word
    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word
    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    // Check if any word starts with the given prefix
    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true

---

Advanced Trie Operations:

1. Delete a Word:

Deleting a word involves a recursive approach, where we remove nodes that are no longer needed.

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isEndOfWord) return false; // Word doesn't exist
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0; // Check if node has children
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth + 1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }

    return false;
}

2. Count Words with a Prefix:

Count how many words start with a given prefix.

countWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return 0;
        node = node.children[char];
    }
    return this._countWords(node);
}

_countWords(node) {
    let count = node.isEndOfWord ? 1 : 0;
    for (let char in node.children) {
        count += this._countWords(node.children[char]);
    }
    return count;
}

3. Autocomplete Suggestions:

Given a prefix, return all words that start with it.

getWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return [];
        node = node.children[char];
    }
    return this._collectWords(node, prefix);
}

_collectWords(node, prefix) {
    let results = [];
    if (node.isEndOfWord) results.push(prefix);

    for (let char in node.children) {
        results = results.concat(this._collectWords(node.children[char], prefix + char));
    }

    return results;
}

---

Time Complexity:

1. Insert: O(L) (L = length of the word)
2. Search: O(L)
3. Prefix Search: O(L)
4. Delete: O(L)

---

Applications of Trie:

1. Autocomplete Systems (e.g., search bars, text editors).
2. Spell Checkers.
3. IP Routing (longest prefix matching).
4. Word Games (e.g., Boggle).
5. DNA Sequence Matching.