Skip to content

Instantly share code, notes, and snippets.

@vickywane
Forked from tpae/Trie.js
Last active Mar 3, 2021
Embed
What would you like to do?
Trie.js - super simple JavaScript implementation
// Trie.js - JS implementation
// https://en.wikipedia.org/wiki/Trie
// Inspired by Tpae's implementation
// we start with the TrieNode
function TrieNode(key) {
// the "key" value will be the character in sequence
this.key = key;
// we keep a reference to parent
this.parent = null;
// we have hash of children
this.children = {};
// check to see if the node is at the end
this.end = false;
}
// iterates through the parents to get the word.
// time complexity: O(k), k = word length
TrieNode.prototype.getWord = function() {
var output = [];
var node = this;
while (node !== null) {
output.unshift(node.key);
node = node.parent;
}
return output.join('');
};
// -----------------------------------------
// we implement Trie with just a simple root with null value.
function Trie() {
this.root = new TrieNode(null);
}
// inserts a word into the trie.
// time complexity: O(k), k = word length
Trie.prototype.insert = function(word) {
var node = this.root; // we start at the root 😬
// for every character in the word
for(var i = 0; i < word.length; i++) {
// check to see if character node exists in children.
if (!node.children[word[i]]) {
// if it doesn't exist, we then create it.
node.children[word[i]] = new TrieNode(word[i]);
// we also assign the parent to the child node.
node.children[word[i]].parent = node;
}
// proceed to the next depth in the trie.
node = node.children[word[i]];
// finally, we check to see if it's the last word.
if (i == word.length-1) {
// if it is, we set the end flag to true.
node.end = true;
}
}
};
// returns every word with given prefix
// time complexity: O(p + n), p = prefix length, n = number of child paths
Trie.prototype.find = function(prefix) {
var node = this.root;
var output = [];
// for every character in the prefix
for(var i = 0; i < prefix.length; i++) {
// make sure prefix actually has words
if (node.children[prefix[i]]) {
node = node.children[prefix[i]];
} else {
// there's none. just return it.
return output;
}
}
// recursively find all words in the node
findAllWords(node, output);
return output;
};
export default Trie
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment