Trie not Tree (Data structure)
Tags: datastructures, javascript, algorithms, trie
Published: 2024-03-20 18:13:17

### Exploring Trie Data Structure in JavaScript

Trie, also known as a prefix tree, is a tree-like data structure that is commonly used to store and retrieve a dynamic set of strings. It offers efficient insertion, deletion, and search operations for strings, making it a popular choice in various applications such as autocomplete systems and spell checkers.

Let's delve into implementing a Trie data structure in JavaScript:

#### Trie Implementation

```javascript
class Node {
    constructor() {
        this.children = {};
        this.endWord = false;
    }
}

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

    // Insertion Operation
    insert(word) {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            let ch = word[i];
            if (!node.children[ch]) {
                node.children[ch] = new Node();
            }
            node = node.children[ch];
        }
        node.endWord = true;
    }

    // Searching Operation
    search(word) {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            let ch = word[i];
            if (!node.children[ch]) {
                return false;
            }
            node = node.children[ch];
        }
        return node.endWord;
    }

    // Deletion Operation
    delete(word) {
        this._delete(this.root, word, 0);
    }

    _delete(node, word, index) {
        if (index === word.length) {
            if (!node.endWord) {
                return false;
            }
            node.endWord = false;
            return !Object.keys(node.children).length === 0;
        }
        let ch = word[index];
        let chNode = node.children[ch];
        if (chNode == null) {
            return false;
        }
        let shouldDeleteCurrentNode = this._delete(chNode, word, index + 1);
        if (shouldDeleteCurrentNode) {
            delete node.children[ch];
        }
        return !Object.keys(node.children).length;
    }

    // Finding Words with Prefix
    findWordWithPrefix(prefix) {
        let node = this.root;
        for (let ch of prefix) {
            if (!node.children[ch]) {
                return [];
            }
            node = node.children[ch];
        }
        return this.findAllWords(node, prefix);
    }

    findAllWords(node, prefix) {
        let words = [];
        if (node.endWord) {
            words.push(prefix);
        }
        for (let ch in node.children) {
            words.push(...this.findAllWords(node.children[ch], prefix + ch));
        }
        return words;
    }

    // Finding Longest Word
    findLongestWord() {
        return this.findLongest(this.root, "");
    }

    findLongest(node, word) {
        let longestWord = node.endWord ? word : "";
        for (let ch in node.children) {
            let childLongestWord = this.findLongest(node.children[ch], word + ch);
            if (childLongestWord.length > longestWord.length) {
                longestWord = childLongestWord;
            }
        }
        return longestWord;
    }
}

// Usage Example
const t = new Trie();
t.insert("apple");
t.insert("applecyder");
t.insert("orange");
console.log(t.search("apple")); // Output: true
t.delete("apple");
console.log(t.search("apple")); // Output: false
console.log(t.findWordWithPrefix("app")); // Output: ["applecyder"]
console.log(t.findLongestWord()); // Output: "applecyder"
```

#### Conclusion

In conclusion, Trie data structure proves to be an efficient solution for storing and managing collections of strings. While insertion and searching operations are straightforward, deletion can be a bit more challenging due to the need for node traversal. Nonetheless, Tries offer immense value, especially in scenarios where fast prefix-based searches or autocomplete functionalities are required.

For a deeper understanding and to explore the implementation details, you can find the complete code in my GitHub repository:

[GitHub Repository: Trie Data Structure](https://github.com/ajithr116/Data-Structures/tree/DSA2/14-trie)

Feel free to experiment with this implementation and incorporate it into your projects for enhanced string manipulation capabilities.

Happy coding!

---