trie.js

trie-fp.js

class Trie {
  head = {
    key: "",
    children: {}
  };

  add(key) {
    var curNode = this.head,
      newNode = null,
      curChar = key.slice(0, 1);

    key = key.slice(1);

    while (
      typeof curNode.children[curChar] !== "undefined" &&
      curChar.length > 0
    ) {
      curNode = curNode.children[curChar];
      curChar = key.slice(0, 1);
      key = key.slice(1);
    }

    while (curChar.length > 0) {
      newNode = {
        key: curChar,
        value: key.length === 0 ? null : undefined,
        children: {}
      };

      curNode.children[curChar] = newNode;

      curNode = newNode;

      curChar = key.slice(0, 1);
      key = key.slice(1);
    }
  }

  search(key) {
    var curNode = this.head,
      curChar = key.slice(0, 1),
      d = 0;

    key = key.slice(1);

    while (
      typeof curNode.children[curChar] !== "undefined" &&
      curChar.length > 0
    ) {
      curNode = curNode.children[curChar];
      curChar = key.slice(0, 1);
      key = key.slice(1);
      d += 1;
    }

    if (curNode.value === null && key.length === 0) {
      return d;
    } else {
      return -1;
    }
  }

  remove(key) {
    var d = this.search(key);
    if (d > -1) {
      removeH(this.head, key, d);
    }
  }
}

function removeH(node, key, depth) {
  if (depth === 0 && Object.keys(node.children).length === 0) {
    return true;
  }

  var curChar = key.slice(0, 1);

  if (removeH(node.children[curChar], key.slice(1), depth - 1)) {
    delete node.children[curChar];
    if (Object.keys(node.children).length === 0) {
      return true;
    } else {
      return false;
    }
  } else {
    return false;
  }
}

trie.js

class Trie {
  head = {
    key: "",
    children: {}
  };

  add(key) {
    var curNode = this.head,
      newNode = null,
      curChar = key.slice(0, 1);

    key = key.slice(1);

    while (
      typeof curNode.children[curChar] !== "undefined" &&
      curChar.length > 0
    ) {
      curNode = curNode.children[curChar];
      curChar = key.slice(0, 1);
      key = key.slice(1);
    }

    while (curChar.length > 0) {
      newNode = {
        key: curChar,
        value: key.length === 0 ? null : undefined,
        children: {}
      };

      curNode.children[curChar] = newNode;

      curNode = newNode;

      curChar = key.slice(0, 1);
      key = key.slice(1);
    }
  }

  search(key) {
    var curNode = this.head,
      curChar = key.slice(0, 1),
      d = 0;

    key = key.slice(1);

    while (
      typeof curNode.children[curChar] !== "undefined" &&
      curChar.length > 0
    ) {
      curNode = curNode.children[curChar];
      curChar = key.slice(0, 1);
      key = key.slice(1);
      d += 1;
    }

    if (curNode.value === null && key.length === 0) {
      return d;
    } else {
      return -1;
    }
  }

  remove(key) {
    var d = this.search(key);
    if (d > -1) {
      removeH(this.head, key, d);
    }
  }
}

function removeH(node, key, depth) {
  if (depth === 0 && Object.keys(node.children).length === 0) {
    return true;
  }

  var curChar = key.slice(0, 1);

  if (removeH(node.children[curChar], key.slice(1), depth - 1)) {
    delete node.children[curChar];
    if (Object.keys(node.children).length === 0) {
      return true;
    } else {
      return false;
    }
  } else {
    return false;
  }
}