Trie Search Operation in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the Trie search for 'cat'?

Given the following Trie implementation and insertions, what will be the output of searching for the word 'cat'?

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('cat'));

A true

B TypeError

C undefined

D false

💡 Hint

Check if the search method returns true only when the word is fully present and marked as end of word.

The word 'cat' was inserted into the Trie and marked as an end of a word. The search method returns true when the full word is found and the last node is marked as end of word.

❓ Predict Output

intermediate

What is the output of searching for 'ca' in the Trie?

Using the same Trie from the previous example, what will be the output of searching for the word 'ca'?

DSA Javascript

console.log(trie.search('ca'));

A true

B false

C undefined

D TypeError

💡 Hint

Remember that 'ca' is a prefix but not a complete word inserted.

The search method returns false because 'ca' is only a prefix in the Trie, not marked as an end of a word.

🧠 Conceptual

advanced

Which statement about Trie search operation is correct?

Choose the correct statement about how the search operation works in a Trie data structure.

A Search returns true if all characters of the word are found in sequence and the last node is marked as end of word.

B Search returns true if the word is a prefix of any inserted word, regardless of end of word marking.

C Search returns true if the first character of the word is found in the Trie root children.

D Search returns true only if the word length is greater than 5 characters.

💡 Hint

Think about what makes a word complete in a Trie.

A Trie search returns true only if the entire word is found character by character and the last character node is marked as the end of a word.

🔧 Debug

advanced

What error occurs when searching for a word with a missing character node?

Consider the Trie search method. What happens if the search word contains a character not present in the Trie nodes?

DSA Javascript

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

A Returns undefined

B Throws a ReferenceError

C Returns false indicating word not found

D Throws a TypeError

💡 Hint

Check the condition when a character node is missing.

The search method returns false immediately when a character node is missing, indicating the word is not present.

🚀 Application

expert

How many words are found after inserting and searching in the Trie?

After inserting the words ['apple', 'app', 'application', 'bat', 'bath'] into an empty Trie, how many of these words will return true when searched?

DSA Javascript

const trie = new Trie();
['apple', 'app', 'application', 'bat', 'bath'].forEach(word => trie.insert(word));

const results = ['apple', 'app', 'application', 'bat', 'bath'].map(word => trie.search(word));
const count = results.filter(Boolean).length;
console.log(count);

A 4

B 2

C 3

D 5

💡 Hint

All inserted words are marked as end of word nodes.

All inserted words are present and marked as complete words, so all searches return true, count is 5.