Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Trie.js - super simple JavaScript implementation
// Trie.js - super simple JS implementation
// https://en.wikipedia.org/wiki/Trie
// -----------------------------------------
// 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;
}
}
};
// check if it contains a whole word.
// time complexity: O(k), k = word length
Trie.prototype.contains = function(word) {
var node = this.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 exists, proceed to the next depth of the trie.
node = node.children[word[i]];
} else {
// doesn't exist, return false since it's not a valid word.
return false;
}
}
// we finished going through all the words, but is it a whole word?
return node.end;
};
// 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;
};
// recursive function to find all words in the given node.
function findAllWords(node, arr) {
// base case, if node is at a word, push to output
if (node.end) {
arr.unshift(node.getWord());
}
// iterate through each children, call recursive findAllWords
for (var child in node.children) {
findAllWords(node.children[child], arr);
}
}
// -----------------------------------------
// instantiate our trie
var trie = new Trie();
// insert few values
trie.insert("hello");
trie.insert("helium");
// check contains method
console.log(trie.contains("helium")); // true
console.log(trie.contains("kickass")); // false
// check find method
console.log(trie.find("hel")); // [ 'helium', 'hello' ]
console.log(trie.find("hell")); // [ 'hello' ]
@PantherHawk

This comment has been minimized.

Copy link

@PantherHawk PantherHawk commented Jan 8, 2018

Thank you!

@asalem1

This comment has been minimized.

Copy link

@asalem1 asalem1 commented Sep 6, 2018

This is really great, thanks!

@ejabx

This comment has been minimized.

Copy link

@ejabx ejabx commented Sep 17, 2018

Great code! It's easy to follow and the examples are a plus.

@ykyuen

This comment has been minimized.

Copy link

@ykyuen ykyuen commented Feb 20, 2019

Thanks~

@omzeton

This comment has been minimized.

Copy link

@omzeton omzeton commented Apr 30, 2019

This is fantastic. thanks for sharing!

@KalpasWang

This comment has been minimized.

Copy link

@KalpasWang KalpasWang commented Sep 30, 2019

thanks! very useful

@Tamplier2911

This comment has been minimized.

Copy link

@Tamplier2911 Tamplier2911 commented Oct 14, 2019

Thank you.

@Tamplier2911

This comment has been minimized.

Copy link

@Tamplier2911 Tamplier2911 commented Oct 14, 2019

remove method is missing, but I found nice example here:
https://kevinwin.com/blog/How-to-implement-a-Trie-in-JavaScript/

I refactored it a bit, so it matches Trie in this example at top, hope anyone can make use of it, have a nice day!

remove(word) {
    if (!word) return null;
    let node = this.root;
    const chain = [];
```

    // traverse down trie
    for (let i = 0; i < word.length; i++) {
      if (node.children[word[i]]) {
        // we want all nodes accessible in chain
        // so we can move backwards and remove dangling nodes
        chain.push(node);
        node = node.children[word[i]];
      } else {
        // word is not in the trie
        return null;
      }
    }

    // if any children, we should only change end flag
    if (Object.keys(node.children).length) {
      node.end = false;
      return node;
    }

    // zero children in node
    // continue untill we hit a breaking condition
    let child = chain.length ? chain.pop() : null; // whatever node was
    let parent = chain.length ? chain.pop() : null; // if node has parent

    while (true) {
      // remove child
      child && parent && delete parent.children[child.key];

      // if more children or chain is empty, we're done!
      if (
        Object.keys(parent.children).length ||
        !chain.length
      ) {
        node.end = false;
        return node;
      }
      // otherwise, we have no more children for our parent and we should keep deleting nodes
      // our next parent is what we pop from the chain
      // our child is what our parent was
      child = parent;
      parent = chain.pop();
    }
  }`
@Wahba1414

This comment has been minimized.

Copy link

@Wahba1414 Wahba1414 commented Nov 10, 2019

Brilliant .. thanks

@Cxarli

This comment has been minimized.

Copy link

@Cxarli Cxarli commented Apr 16, 2020

Could you please attach a license to this gist? If you don't care about it anymore, it would help if you could use The Unlicense since the default is that others are not allowed to use it for anything.

@flopperj

This comment has been minimized.

Copy link

@flopperj flopperj commented May 1, 2020

Awesome implementation of the Trie, here's my approach at implementing the remove method.

/**
 * Removes word from trie
 * Time complexity = O(nlogn)
 * Space complexity = O(n)
 * @param {string} word
 */
Trie.prototype.remove = function (word) {
    let root = this.root;

    if(!word) return;

    // recursively finds and removes a word
    const removeWord = (node, word) => {

        // check if current node contains the word
        if (node.end && node.getWord() === word) {

            // check and see if node has children
            let hasChildren = Object.keys(node.children).length > 0;

            // if has children we only want to un-flag the end node that marks end of a word.
            // this way we do not remove words that contain/include supplied word
            if (hasChildren) {
                node.end = false;
            } else {
                // remove word by getting parent and setting children to empty dictionary
                node.parent.children = {};
            }

            return true;
        }

        // recursively remove word from all children
        for (let key in node.children) {
            removeWord(node.children[key], word)
        }

        return false
    };

    // call remove word on root node
    removeWord(root, word);
};
@harshith-venkatesh

This comment has been minimized.

Copy link

@harshith-venkatesh harshith-venkatesh commented Aug 8, 2020

This is amazing!

@by12380

This comment has been minimized.

Copy link

@by12380 by12380 commented Sep 24, 2020

Thanks for the contribution! Just wanted to point out that unshift() in getWord() is not very efficient. unshift() is a O(n) operation and will lead to O(k^2) for getWord(). We would rather do push() and then reverse() in the end.

@AndrewKnutsen

This comment has been minimized.

Copy link

@AndrewKnutsen AndrewKnutsen commented Oct 13, 2020

I'm too new to JS not to ask: does this need a destroy() method of some sort?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment