DEV Community

Ajith R
Ajith R

Posted on

Trie not Tree (Data structure)

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

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"
Enter fullscreen mode Exit fullscreen mode

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

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

Happy coding!


Top comments (0)