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

vartrieNode=function(){this.children={}this.end=false}

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

For the case of insert

Trie.prototype.insert=function(word){letroot=this.rootfor(letterofword){if(root.children[letter]){root=root.children[letter]}else{root.children[letter]=newtrieNode()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){letroot=this.rootfor(letterofword){if(root.children[letter]){root=root.children[letter]}else{returnfalse}}returnroot.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:

vartrieNode=function(){this.children={}this.end=false}varTrie=function(){this.root=newtrieNode()};Trie.prototype.insert=function(word){letroot=this.rootfor(letterofword){if(root.children[letter]){root=root.children[letter]}else{root.children[letter]=newtrieNode()root=root.children[letter]}}root.end=true};Trie.prototype.search=function(word){letroot=this.rootfor(letterofword){if(root.children[letter]){root=root.children[letter]}else{returnfalse}}returnroot.end};Trie.prototype.startsWith=function(prefix){letroot=this.rootfor(letterofprefix){if(root.children[letter]){root=root.children[letter]}else{returnfalse}}returntrue};