Implement Trie (Prefix Tree) - LeetCode

What is Trie?

Trie (or prefix tree) is a data structure, which is used for retrieval of a key in a dataset of a strings

Trie is used for AutoCompletion (google search), Spell Checker etc

Trie is a rooted structure, something like below which represents DEV

root = {children: {
    d: {
        children: {
            e: {
                children: {
                    v: {}
                }
            }
        }
    }
}}

Every character will hold children which can be extended

Let's create a Data Structure for trieNode

var trieNode = function() {
    this.children = {}
    this.end = false
}

Now we have children, which can store letters as a tree and we need end to differentiate whether the word provided in search has ended or not

For the case of insert

Trie.prototype.insert = function(word) {
    let root = this.root
    for(letter of word) {
        if(root.children[letter]) {
            root = root.children[letter]
        } else {
            root.children[letter] = new trieNode()
            root = root.children[letter]
        }
    }
    root.end = true
};

We loop through each letter of the word and if it exists in trieNode, we update root to root.children[letter] else we create a new trieNode at root.children[letter] and then assign root to root.children[letter]

After the loop, set root.end to true to denote it's a word

For the case of search

Trie.prototype.search = function(word) {
    let root = this.root
    for(letter of word) {
        if(root.children[letter]) {
            root = root.children[letter]
        } else {
            return false
        }
    }
    return root.end
};

We implement same solution but to check whether the letter exists in the trieNode, if it doesn't return false. If it exists check whether that's the end of the node.

For the case of startsWith

This is same as search but at the end of the loop you don't have to check whether end of trieNode is true or not

Here's the Code:

var trieNode = function() {
    this.children = {}
    this.end = false
}

var Trie = function() {
    this.root = new trieNode()
};

Trie.prototype.insert = function(word) {
    let root = this.root
    for(letter of word) {
        if(root.children[letter]) {
            root = root.children[letter]
        } else {
            root.children[letter] = new trieNode()
            root = root.children[letter]
        }
    }
    root.end = true
};

Trie.prototype.search = function(word) {
    let root = this.root
    for(letter of word) {
        if(root.children[letter]) {
            root = root.children[letter]
        } else {
            return false
        }
    }
    return root.end
};

Trie.prototype.startsWith = function(prefix) {
    let root = this.root
    for(letter of prefix) {
        if(root.children[letter]) {
            root = root.children[letter]
        } else {
            return false
        }
    }
    return true
};