Sunday, December 28, 2008

JavaScript Trie Implementation

I've been laying around the house this weekend hacking away at little side projects. Here is one of my tangents. Perhaps someone out there will give this little guy a nice home, maybe a Bag implementation or a drop down list for an auto suggest enabled form field.

The Test (and how to use it)

function testThoughtWorks() { 
var trie = new byrne.TrieNode(/* root */);

assertEquals(1, trie.getWordCount('thought'));
assertEquals(0, trie.getPrefixCount('thought'));


assertEquals(1, trie.getWordCount('thought'));
assertEquals(1, trie.getPrefixCount('thought'));
assertEquals(1, trie.getWordCount('thoughtworks'));
assertEquals(0, trie.getPrefixCount('thoughtworks'));
assertEquals(0, trie.getWordCount('foo'));
assertEquals(0, trie.getPrefixCount('foo'));

The Implementation

byrne = {}; // create the namespace

* @see
* @author Dennis Byrne
* @constructor
byrne.TrieNode = function(){
this.wordCount = 0;
this.prefixCount = 0;
this.children = [];

byrne.TrieNode.prototype.add = function(word) {
var k = word.charAt(0);
(this.children[k] || (this.children[k] = new byrne.TrieNode()))

* Retrieve the prefix count of the applied argument w/ recursion.
byrne.TrieNode.prototype.getPrefixCount = function(word){
return word ?
this.getCount(word, arguments.callee) : this.prefixCount;

* Retrieve the word count of the applied argument w/ recursion.
byrne.TrieNode.prototype.getWordCount = function(word){
return word ?
this.getCount(word, arguments.callee) : this.wordCount;

* @private
byrne.TrieNode.prototype.getCount = function(word, method){
var k = word.charAt(0);
return this.children[k] ?[k], word.substring(1)) : 0;


Jalada said...

Completely forgot to post this here, but we've been using this at to power the exclusions filter. I wrote a blog post about it:

raga said...

Can any one tell how to write a plugin for mozila?
i went through various sites..was'nt helpful though said...

I created an implementation of a Trie in JS here:
Your blog post is duly noted there as inspiration, because you were truly the only one I could find that implemented it in the most correct manner.
Thank you for posting your findings and work over here, I hope to contribute back with my implementation.


Mike de Boer.

Pavel Co Ebele said...

Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Front end developer learn from Javascript Training in Chennai . or Javascript Training in Chennai. Nowadays JavaScript has tons of job opportunities on various vertical industry. ES6 Training in Chennai