Assignment 13 Frequently Asked Questions

A good implementation of a TRIE is

const TrieNode = function (key) {
  this.key = key;
  this.parent = null;
  this.children = {};
  this.end = false;
  }
  
const Trie = function() {
  this.root = new TrieNode(null);
}    
  
TrieNode.prototype.getWord = function() {
  let output = [];
  let node = this;
  while (node !== null) {
     output.unshift(node.key);
     node = node.parent;
    }
    return "<br> " + output.join('');
  }

 Trie.prototype.insert = function(word) {
    let node = this.root; 

    for(let i = 0; i < word.length; i++) {
      if (!node.children[word[i]]) {
        node.children[word[i]] = new TrieNode(word[i]);
        node.children[word[i]].parent = node;
      }
      node = node.children[word[i]];
      if (i == word.length-1) {
        node.end = true;
      }
    }
 } 
  
Trie.prototype.contains = function(word) {
    let node = this.root;

    for(let i = 0; i < word.length; i++) {
      if (node.children[word[i]]) {
        node = node.children[word[i]];
      } else {
        return false;
      }
    }
    return node.end;
  }

 Trie.prototype.prefix = function(prefix) {
    let node = this.root;
    let output = [];

    for(let i = 0; i < prefix.length; i++) {
      if (node.children[prefix[i]]) {
        node = node.children[prefix[i]];
      } else {
        return output;
      }
    }

    findAllWords(node, output);
    output.sort();
    return output;
  }
  
  const findAllWords = (node, arr) => {
    if (node.end) {
      arr.unshift(node.getWord());
    }
    for (let child in node.children) {
      findAllWords(node.children[child], arr);
    }
  }