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.