Word Search in Trie in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Searching a Word in Trie

What is the output of the following code that inserts words into a Trie and searches for a specific word?

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }
}

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('dog');
console.log(trie.search('car'));

A true

B undefined

C false

D TypeError

💡 Hint

Check if the word 'car' was inserted and if the search method returns true only for complete words.

The word 'car' was inserted into the Trie. The search method returns true only if the word exists and the last node marks the end of a word.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the role of the 'isEndOfWord' property in a Trie node?

A It counts how many words pass through this node.

B It marks the node as the end of a valid word stored in the Trie.

C It stores the character value of the node.

D It points to the parent node in the Trie.

💡 Hint

Think about how the Trie knows when a word ends.

The 'isEndOfWord' boolean indicates that the path to this node forms a complete word stored in the Trie.

🔧 Debug

advanced

Identify the Error in Trie Search Method

What error will occur when running this code snippet that searches for a word in a Trie?

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }
}

const trie = new Trie();
trie.insert('apple');
console.log(trie.search('app'));

A TypeError

B true

C false

D undefined

💡 Hint

Check if 'app' was inserted as a complete word or just a prefix.

The word 'app' was not inserted as a complete word, only 'apple' was. So search returns false.

🚀 Application

advanced

Result of Inserting and Searching Multiple Words

After inserting the words ['bat', 'bath', 'batman', 'batmobile'] into an empty Trie, what will be the output of searching for 'batm'?

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }
}

const trie = new Trie();
['bat', 'bath', 'batman', 'batmobile'].forEach(word => trie.insert(word));
console.log(trie.search('batm'));

A false

B TypeError

C undefined

D true

💡 Hint

Check if 'batm' was inserted as a complete word or just a prefix.

'batm' is a prefix of 'batman' and 'batmobile' but not a complete word itself, so search returns false.

🧠 Conceptual

expert

Trie Memory Usage and Optimization

Which of the following statements about Trie memory usage and optimization is correct?

A Using arrays instead of objects for children always reduces Trie memory usage.

B Tries always use less memory than hash tables because they share prefixes.

C Tries cannot be optimized for memory and always use large amounts of space.

D Compressed Tries reduce memory by merging nodes with a single child into one node.

💡 Hint

Think about how nodes with only one child can be merged to save space.

Compressed Tries (or Radix Trees) merge chains of single-child nodes to reduce memory usage.