The above diagram shows a trie which stores the words “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, and “inn”.<\/p>\n Below is my implementation of Trie in javascript:<\/strong><\/p>\n At each node of Trie, I store the word-count, prefix-count and the link to children.<\/p>\n To insert a word, I recursively traverse through the trie nodes if they already exist, else I create new nodes. While traversing the nodes, I keep on storing the information in the nodes as I encounter each character in the given string.<\/p>\n Removing a word follows the similar idea as insertion.<\/p>\n To update, I simply remove the existing word and insert the new word.<\/p>\n Searching a word is trivial as we just need to check if the word count at the terminating node of the input string is greater than zero or not.<\/p>\n You can get the full source code in my GitHub repository<\/a><\/p>\n Meanwhile you can see the auto-complete demo using my trie implementation<\/a><\/p>\n Links:<\/strong><\/p>\n A trie, or prefix tree, is a multi-way tree structure useful for storing strings over an alphabet. It is very efficient and handy and can be used for various purposes like auto-complete, spell-check, dictionary search, etc. The basic idea of a Trie goes as below: We have a root node which represents an empty string.…<\/p>\n Read More<\/span> Trie implementation in Javascript<\/span><\/a>","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[19,10],"class_list":["entry","author-saurabh","post-155","post","type-post","status-publish","format-standard","category-programming","tag-algorithms","tag-javascript"],"_links":{"self":[{"href":"https:\/\/odhyan.com\/blog\/wp-json\/wp\/v2\/posts\/155","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/odhyan.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/odhyan.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/odhyan.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/odhyan.com\/blog\/wp-json\/wp\/v2\/comments?post=155"}],"version-history":[{"count":42,"href":"https:\/\/odhyan.com\/blog\/wp-json\/wp\/v2\/posts\/155\/revisions"}],"predecessor-version":[{"id":402,"href":"https:\/\/odhyan.com\/blog\/wp-json\/wp\/v2\/posts\/155\/revisions\/402"}],"wp:attachment":[{"href":"https:\/\/odhyan.com\/blog\/wp-json\/wp\/v2\/media?parent=155"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/odhyan.com\/blog\/wp-json\/wp\/v2\/categories?post=155"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/odhyan.com\/blog\/wp-json\/wp\/v2\/tags?post=155"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"Trie](\"http:\/\/en.wikipedia.org\/wiki\/File:Trie_example.svg\")
<\/a><\/p>\n\r\nTrie = function() {\r\n this.words = 0;\r\n this.prefixes = 0;\r\n this.children = [];\r\n};\r\n<\/pre>\n\r\ninsert: function(str, pos) {\r\n if(str.length == 0) { \/\/blank string cannot be inserted\r\n return;\r\n }\r\n var T = this,\r\n k,\r\n child;\r\n if(pos === undefined) {\r\n pos = 0;\r\n }\r\n if(pos === str.length) {\r\n T.words ++;\r\n return;\r\n }\r\n T.prefixes ++;\r\n k = str[pos];\r\n if(T.children[k] === undefined) { \/\/if node for this char doesn't exist, create one\r\n T.children[k] = new Trie();\r\n }\r\n child = T.children[k];\r\n child.insert(str, pos + 1);\r\n}\r\n<\/pre>\n\r\nfind: function(str) {\r\n if(str.length == 0) {\r\n return false;\r\n }\r\n if(this.countWord(str) > 0) {\r\n return true;\r\n } else {\r\n return false;\r\n }\r\n}\r\n<\/pre>\n\n