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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Search for a Word

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

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true;
  }

  search(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char)!;
    }
    return node.isEndOfWord;
  }
}

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

A TypeError

B false

C undefined

D true

💡 Hint

Think about whether the word 'app' was inserted and if the search checks for complete words.

The word 'app' was inserted into the Trie, so searching for 'app' returns true. The search method returns true only if the word exists and is marked as an end of a word.

❓ Predict Output

intermediate

Trie Search Result for a Non-Inserted Word

What will be the output of the following code when searching for a word not inserted into the Trie?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true;
  }

  search(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char)!;
    }
    return node.isEndOfWord;
  }
}

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

A true

B false

C undefined

D ReferenceError

💡 Hint

Check if 'cap' was inserted or if the search path exists in the Trie.

The word 'cap' was not inserted. The search fails because the character 'p' is not found after 'ca', so the method returns false.

🔧 Debug

advanced

Identify the Bug in Trie Search Method

What error will the following TypeScript code produce when searching for a word, and why?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true;
  }

  search(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      node = node.children.get(char)!;
    }
    return node.isEndOfWord;
  }
}

const trie = new Trie();
trie.insert("dog");
console.log(trie.search("don"));

A SyntaxError

B true

C TypeError: Cannot read property 'isEndOfWord' of undefined

D false

💡 Hint

Look at what happens if a character is missing in the children map during search.

The search method does not check if the character exists in the children map before accessing it. When searching for 'don', the character 'o' is found, but the next character 'n' is missing, so accessing undefined causes a TypeError.

🚀 Application

advanced

Number of Words Stored in Trie

Given the following Trie implementation and inserted words, what is the total number of words stored in the Trie?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true;
  }

  countWords(node: TrieNode = this.root): number {
    let count = 0;
    if (node.isEndOfWord) count++;
    for (const child of node.children.values()) {
      count += this.countWords(child);
    }
    return count;
  }
}

const trie = new Trie();
trie.insert("bat");
trie.insert("bath");
trie.insert("batman");
trie.insert("bat");
trie.insert("batch");
console.log(trie.countWords());

A 4

B 5

C 3

D 6

💡 Hint

Duplicates do not increase the count. Count only unique complete words.

The words inserted are 'bat', 'bath', 'batman', 'bat' (duplicate), and 'batch'. The duplicate 'bat' does not add to the count. So total unique words stored are 4.

🧠 Conceptual

expert

Why Use Trie for Word Search?

Which of the following is the main advantage of using a Trie data structure for word search compared to a simple list of words?

A Tries allow searching words in O(m) time where m is the length of the word, independent of the number of words stored.

B Tries use less memory than storing words in a list because they compress all words into a single string.

C Tries can store infinite words without increasing search time.

D Tries automatically sort words alphabetically without extra processing.

💡 Hint

Think about how search time depends on word length and number of stored words.

Tries provide search time proportional to the length of the word (O(m)), not the number of words stored, making them efficient for prefix-based searches. They do not necessarily use less memory or automatically sort words, and search time can increase with word length.

Practice

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

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To store words in a linked list format

D. To perform arithmetic operations on words

Solution

1. Step 1: Understand the Trie structure

   A Trie stores characters in a tree where each path represents a prefix of words.

2. Step 2: Identify the use in word search

   This structure allows quick prefix-based search, making it efficient for word search problems.

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 prefixes and fast word lookup [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie stores words linearly
• Assuming Trie performs arithmetic

2. Which of the following is the correct TypeScript syntax to declare a Trie node class with a children map and an end-of-word boolean?

easy

A. class TrieNode { children: Map; isEndOfWord: boolean; constructor() { this.children = new Map(); this.isEndOfWord = false; } }

B. class TrieNode { children: string[]; isEndOfWord: number; constructor() { this.children = []; this.isEndOfWord = 0; } }

C. class TrieNode { children: Map; isEndOfWord: boolean; constructor() { this.children = new Map(); this.isEndOfWord = true; } }

D. class TrieNode { children: object; isEndOfWord: string; constructor() { this.children = {}; this.isEndOfWord = 'false'; } }

Solution

1. Step 1: Check children type

   Children should be a Map from string to TrieNode for efficient character mapping.

2. Step 2: Check isEndOfWord type and initialization

   It should be a boolean initialized to false to mark word endings correctly.

3. Final Answer:

   class TrieNode { children: Map; isEndOfWord: boolean; constructor() { this.children = new Map(); this.isEndOfWord = false; } } -> Option A

4. Quick Check:

   Correct types and initialization [OK]

Hint: Use Map and boolean for end flag [OK]

Common Mistakes:

• Using array instead of Map for children
• Using wrong types for isEndOfWord
• Initializing isEndOfWord incorrectly

3. Given the following TypeScript code snippet for searching a word in a Trie, what will be the output when searching for the word "cat" if only "car" and "cap" are inserted?

class TrieNode {
  children = new Map();
  isEndOfWord = false;
}

class Trie {
  root = new TrieNode();

  insert(word: string) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
    }
    node.isEndOfWord = true;
  }

  search(word: string): boolean {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch)!;
    }
    return node.isEndOfWord;
  }
}

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

medium

A. true

B. false

C. undefined

D. Runtime error

Solution

1. Step 1: Trace insertion of "car" and "cap"

   Both words create nodes for 'c', 'a', then diverge at 'r' and 'p' respectively, marking those ends as true.

2. Step 2: Trace search for "cat"

   Search finds 'c' and 'a', but 't' is not a child of 'a', so search returns false.

3. Final Answer:

   false -> Option B

4. Quick Check:

   Word not inserted = false [OK]

Hint: If last char missing, search returns false [OK]

Common Mistakes:

• Assuming partial prefix means true
• Confusing isEndOfWord with node existence
• Expecting undefined instead of false

4. Identify the bug in the following TypeScript Trie search method that causes it to always return false:

search(word: string): boolean {
  let node = this.root;
  for (const ch of word) {
    if (!node.children.has(ch)) return false;
    node = node.children.get(ch)!;
  }
  return node.isEndOfWord === false;
}

medium

A. The method should return true before the loop ends

B. The loop should iterate backwards over the word

C. The children map should be an array instead

D. The return condition should be node.isEndOfWord, not its negation

Solution

1. Step 1: Analyze the return statement

   The method returns node.isEndOfWord === false, which means it returns true if the word is NOT ending here.

2. Step 2: Correct the return logic

   It should return node.isEndOfWord to confirm the word ends at this node.

3. Final Answer:

   The return condition should be node.isEndOfWord, not its negation -> Option D

4. Quick Check:

   Return true if word ends here [OK]

Hint: Return node.isEndOfWord directly to confirm word end [OK]

Common Mistakes:

• Returning negation of isEndOfWord
• Changing loop direction unnecessarily
• Using wrong data structure for children

5. You want to implement a function that finds all words in a Trie starting with a given prefix. Which approach correctly combines Trie traversal and backtracking to collect all matching words?

hard

A. Search each word in the Trie individually to check prefix match

B. Store all words in an array and filter by prefix each time

C. Traverse Trie nodes for prefix, then recursively collect words from that node using backtracking

D. Use a hash map to map prefixes to words without Trie traversal

Solution

1. Step 1: Traverse Trie to prefix node

   Follow characters of prefix to reach the node representing last prefix character.

2. Step 2: Use backtracking from prefix node

   Recursively explore all children nodes to collect complete words starting with prefix.

3. Final Answer:

   Traverse Trie nodes for prefix, then recursively collect words from that node using backtracking -> Option C

4. Quick Check:

   Prefix traversal + backtracking = Traverse Trie nodes for prefix, then recursively collect words from that node using backtracking [OK]

Hint: Find prefix node, then backtrack to collect words [OK]

Common Mistakes:

• Checking all words instead of prefix traversal
• Filtering array instead of Trie traversal
• Using hash map without Trie structure