Challenge 1: Basic Trie - insert and search methods

[winterrdog]

my solutions for EXERCISE 1 − IMPLEMENTING A TRIE (Chapter 7).

After reading through the problem, i came up with my own insert and search functions that are iterative( one stack frame to babysit ) then later viewed the author's solution. Here's are my methods to the problem:

class TrieNode {
  constructor() {
    this.children = {}; // k: string, v: TrieNode
    this.isEndOfWord = false;
  }

  /**
   * adds a given node to the children of the Trie node
   * @param {string} letter character to represent node
   * @param {TrieNode} newNode node to add as a child
   * @param {boolean} endOfWord indicates if it is the last character
   */
  add(letter, newNode, endOfWord) {
    // add node to children
    this.children[letter] = newNode;

    endOfWord && (newNode.isEndOfWord = true);
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  /**
   * Inserts a node into a trie.
   * @param {string} word word to insert.
   * @returns {void}
   */
  insert(word) {
    if (!word.length) return; // sanity check

    for (let i = 0, currNode = this.root; i != word.length; ++i) {
      if (word[i] in currNode.children) {
        currNode = currNode.children[word[i]];
        continue;
      }
      const newNode = new TrieNode(),
        isLastChar = i + 1 === word.length;
      currNode.add(word[i], newNode, isLastChar);
      currNode = newNode;
    }
  }

  /**
   * Searches for a word in the trie.
   * @param {string} word word to search for in the trie
   * @returns {boolean}
   */
  search(word) {
    for (let i = 0, letter = "", currNode = this.root; i != word.length; i++) {
      letter = word[i];
      if (!(letter in currNode.children)) break;

      const isLastChar = i + 1 === word.length,
        node = currNode.children[letter];

      if (isLastChar && node.isEndOfWord) return true;

      currNode = node;
    }

    return false;
  }

  print(o = this.root, indent = 1) {
    if (!o) return;

    let space = "+".repeat(indent);
    for (const letter in o.children) {
      if (Object.hasOwnProperty.call(o.children, letter)) {
        const element = o.children[letter];

        console.log(`${space} ${letter}`);
        this.print(element, (indent += 2));
      }
    }
  }
}

if there's sth that needs a change i'll be glad to listen ( i'll be all ears in fact )

@ishtms thanks a ton for this compilation btw 👍 i luv it 💯

[ishtms]

@winterrdog Your implementation is spot on. I'd like to suggest a couple of potential improvements, but feel free to use whichever style you prefer:

First, consider using explicit if statements instead of logical && when you're not using the return value.

if (endOfWord) newNode.isEndOfWord = true;

instead of

 endOfWord && (newNode.isEndOfWord = true);

Secondly, (and lastly) string/array lengths are more commonly visualized as Array.length - 1. This can be especially helpful for beginners.

const isLastChar = i === word.length - 1

instead of

const isLastChar = i + 1 === word.length

These are just suggestions that you might find helpful, but use whatever style you're most comfortable with.

[winterrdog]

thanks @ishtms !

i am gonna consider these updates.

they make sense because they're more clear to other people reading my code