Trie Search Operation in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Search for Existing Word

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

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');
trie.insert('dog');
console.log(trie.search('cat'));

A TypeError

B false

C undefined

D true

💡 Hint

Think about whether the word 'cat' was inserted before searching.

The word 'cat' was inserted into the Trie, so searching for it returns true.

❓ Predict Output

intermediate

Output of Trie Search for Non-Existing Word

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

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');
trie.insert('dog');
console.log(trie.search('bat'));

A undefined

B true

C false

D ReferenceError

💡 Hint

Check if 'bat' was inserted before searching.

The word 'bat' was not inserted into the Trie, so searching for it returns false.

🧠 Conceptual

advanced

Understanding Trie Search Behavior

In a Trie, what does it mean if the search for a word returns false even though all characters of the word are present in the Trie nodes?

A The word is a prefix but not a complete word stored in the Trie

B The Trie is empty and has no words stored

C The search function has a bug and always returns false

D The word is stored but the search function only checks prefixes

💡 Hint

Think about the difference between a prefix and a complete word in a Trie.

If all characters are found but the isEndOfWord flag is false, it means the searched word is only a prefix, not a full word stored in the Trie.

❓ Predict Output

advanced

Output of Trie Search After Partial Insertions

What is the output of the following TypeScript code that inserts 'car' and 'cart' into a Trie and searches for 'car' and 'cart'?

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('car');
trie.insert('cart');
console.log(trie.search('car'));
console.log(trie.search('cart'));

A true false

B true true

C false true

D false false

💡 Hint

Both 'car' and 'cart' were inserted, so both searches should succeed.

Both words 'car' and 'cart' were inserted, so searching for either returns true.

🔧 Debug

expert

Identify the Bug in Trie Search Implementation

What error will the following TypeScript code produce when searching for the word 'bat' after inserting 'bat' and 'bath' 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('bat');
trie.insert('bath');
console.log(trie.search('bat'));
console.log(trie.search('bath'));
console.log(trie.search('batman'));

A false

B true

C TypeError

D undefined

💡 Hint

Consider what happens when searching for a word that is not inserted but shares a prefix.

Searching for 'batman' returns false because the prefix 'bat' exists but 'batman' was not inserted.