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.

Practice

1. What is the main purpose of using a Trie data structure in word search?

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To store words in a hash table

D. To perform arithmetic operations on words

Solution

1. Step 1: Understand Trie structure

   A Trie stores characters of words in a tree where each node represents a character.

2. Step 2: Identify Trie usage

   It allows quick prefix-based search by traversing nodes matching characters.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is all about prefix-based fast word search [OK]

Common Mistakes:

• Confusing Trie with hash tables
• Thinking Trie sorts words
• Assuming Trie does arithmetic

2. Which of the following is the correct way to check if a word exists in a Trie in JavaScript?

easy

A. Use a loop to traverse nodes matching each character and check end flag

B. Use Array.includes(word) on the Trie object

C. Use JSON.stringify on Trie and search substring

D. Use Math.max on character codes of the word

Solution

1. Step 1: Understand Trie search method

   Search involves traversing nodes for each character and checking if the word ends at last node.

2. Step 2: Eliminate incorrect options

   Array.includes and JSON.stringify are not suitable for Trie structure. Math.max is unrelated.

3. Final Answer:

   Use a loop to traverse nodes matching each character and check end flag -> Option A

4. Quick Check:

   Traverse nodes + check end = correct search [OK]

Hint: Traverse each character node and check end flag [OK]

Common Mistakes:

• Using array methods on Trie
• Trying to convert Trie to string
• Applying math functions on words

3. What will be the output of the following code snippet?

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = 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.isEnd = true;
  }
  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEnd;
  }
}

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

medium

A. false false

B. false true

C. true false

D. true true

Solution

1. Step 1: Insert words 'cat' and 'car'

   Both words are added character by character, marking end nodes for 't' and 'r'.

2. Step 2: Search 'cat' and 'cap'

   'cat' exists with isEnd true, 'cap' path breaks at 'p' missing node, returns false.

3. Final Answer:

   true false -> Option C

4. Quick Check:

   Search 'cat' = true, 'cap' = false [OK]

Hint: Check inserted words and search path carefully [OK]

Common Mistakes:

• Assuming 'cap' exists after inserting 'car'
• Confusing isEnd flag
• Ignoring missing child nodes

4. Identify the bug in the following Trie search method and select the fix:

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

medium

A. Return false at the end instead of true

B. Add a check for empty word before loop

C. Change for loop to while loop

D. Return node.isEnd instead of true to confirm full word match

Solution

1. Step 1: Analyze current search return

   Returns true if path exists but does not check if word ends here.

2. Step 2: Correct return value

   Must return node.isEnd to confirm the word is complete, not just prefix.

3. Final Answer:

   Return node.isEnd instead of true to confirm full word match -> Option D

4. Quick Check:

   Check isEnd flag to confirm word end [OK]

Hint: Always check isEnd flag to confirm full word [OK]

Common Mistakes:

• Returning true without checking isEnd
• Changing loop type unnecessarily
• Ignoring empty word cases

5. Given a list of words, how can you use a Trie to find all words that start with a given prefix efficiently? Choose the best approach.

hard

A. Sort words and use binary search on prefix

B. Insert all words into Trie, traverse prefix nodes, then collect all descendant words

C. Use a hash map with prefix keys for direct lookup

D. Check each word in list if it starts with prefix using string methods

Solution

1. Step 1: Insert all words into Trie

   Build Trie so each word is represented by a path of nodes.

2. Step 2: Traverse prefix nodes and collect words

   Find node matching prefix end, then recursively collect all words below it.

3. Step 3: Compare other options

   Sorting and binary search is possible but less efficient for many queries. Hash maps need many keys. Checking each word is slow.

4. Final Answer:

   Insert all words into Trie, traverse prefix nodes, then collect all descendant words -> Option B

5. Quick Check:

   Trie + prefix traversal = efficient prefix search [OK]

Hint: Use Trie prefix traversal then gather descendant words [OK]

Common Mistakes:

• Ignoring Trie traversal for prefix
• Using slow linear search for prefix
• Confusing hash map with Trie