Tries

A trie or prefix tree is a tree data structure where all descendants of a node have a common prefix. A common usage of a trie is for autocompletion or as an alternative to a hash table. Trie’s are convenient for autocompletion since all completions of a prefix are descendants of the node that represents that prefix. As an alternative to a hash table trie’s provide lookup that is guaranteed to be linear with respect to the length of the key, no need for a hash function or dealing with hash collisions and the ability to iterate over keys in sorted order.

Like other tree data structures each node in a trie contains a value, some children nodes and is itself a trie.

Inserting into a trie recursively adds children to each sub-trie for each character in the string.

var Trie = function(value) {
  this.children = {};
};

Trie.prototype.insert = function(string) {
  var c = string[0];
  var remaining = string.substr(1);
  if (!c) {
    this.children.$ = new Trie();
    return;
  }
  if (!this.children.hasOwnProperty(c)) {
    this.children[c] = new Trie();
  }
  this.children[c].insert(remaining);
};

Finding a key in a trie is done just by walking down the trie using each successive character in the key to find the next child to visit. Generating all completions for some string is done by first finding the node that represents the string then returning all leaves that are descendants of that node.

Trie.prototype._find = function(string, prefix) {
  var c = string[0];
  var remaining = string.substr(1);
  prefix = prefix || '';
  prefix += c;
  if (this.children.hasOwnProperty(c)) {
    if (!remaining) {
      return { trie: this.children[c], prefix: prefix };
    }
    return this.children[c]._find(remaining, prefix);
  }
  return null;
};

Trie.prototype.traverse = function(callback, prefix) {
  prefix = prefix || '';
  Object.keys(this.children).forEach(function(key) {
    callback(prefix + key);
  });
  for (var key in this.children) {
    this.children[key].traverse(callback, prefix + key[0]);
  }
};

Trie.prototype.leaves = function(prefix) {
  prefix = prefix || '';
  var result = [];
  this.traverse(function(value) {
    if (value[value.length - 1]  === '$') {
      result.push(prefix + value.substring(0, value.length - 1));
    }
  });
  return result;
};

Trie.prototype.completions = function(string) {
  var trie = this._find(string);
  if (trie) {
    return trie.trie.leaves(trie.prefix);
  }
  return null;
};

Here’s the example from the wikipedia article:

var trie = new Trie();
var words = ["A", "to", "tea", "ted", "ten", "i", "in", "inn"];
words.forEach(function(word) {
  trie.insert(word);
});
trie.completions('te');
// [ 'tea', 'ted', 'ten' ]

And finally using it with a full dictionary of words:

var fs = require('fs');
var words = fs.readFileSync('/usr/share/dict/words', 'utf-8').split('\n');
var trie = new Trie();
for (var i = 0; i < words.length; i++) {
  trie.insert(words[i]);
}
trie.completions('burri');
// ['burring', 'burrito', 'burrito\'s', 'burritos']