Prefix Search Using Trie in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A.children.delete(char)

B.children.set(char)

C.children.has(char)

D.children.get(char)

Attempts:

3 left

💡 Hint

Common Mistakes

Using set instead of get to move to the child node.

Trying to check if the child exists instead of moving to it.

We move to the child node corresponding to the current character using node.children.get(char).

2fill in blank

medium

Complete the code to check if a prefix exists in the Trie.

DSA Typescript

startsWith(prefix: string): boolean {
  let node = this.root;
  for (const char of prefix) {
    if (!node.children.has(char)) {
      return false;
    }
    node = node[1];
  }
  return true;
}

Drag options to blanks, or click blank then click option'

A.children.set(char)

B.children.get(char)

C.children.has(char)

D.children.delete(char)

Attempts:

3 left

💡 Hint

Common Mistakes

Using set instead of get to move to the child node.

Checking for existence but not moving to the child node.

To traverse the Trie for each character in the prefix, we use node.children.get(char).

3fill in blank

hard

Fix the error in the search method to correctly check if a word exists in the Trie.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A.children.get(char)

B.children.set(char)

C.children.has(char)

D.children.delete(char)

Attempts:

3 left

💡 Hint

Common Mistakes

Using set instead of get to move to the child node.

Not moving to the child node after checking existence.

We must move to the child node for each character using node.children.get(char) to check the word properly.

4fill in blank

hard

Complete the code to implement a method that collects all words starting from a given node.

DSA Typescript

private collectWords(node: TrieNode, prefix: string, words: string[]) {
  if (node.isEndOfWord) {
    words.push(prefix);
  }
  for (const [char, childNode] of node.children) {
    this.collectWords(childNode, prefix[1] char, words,);
  }
}

Drag options to blanks, or click blank then click option'

A+

B,

C.

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using '.' instead of '+' to concatenate strings.

Using '.' instead of ',' to separate function arguments.

We concatenate the character to the prefix using '+' and pass the words array as the second argument separated by a comma.

5fill in blank

hard

Fill both blanks to implement the prefix search method that returns all words starting with the given prefix.

DSA Typescript

prefixSearch(prefix: string): string[] {
  let node = this.root;
  for (const char of prefix) {
    if (!node.children.has(char)) {
      return [];
    }
    node = node[1];
  }
  const words: string[] = [];
  this.collectWords(node, prefix[2], words,);
  return words;
}

Drag options to blanks, or click blank then click option'

A.children.get(char)

B+

C,

D.children.has(char)

Attempts:

3 left

💡 Hint

Common Mistakes

Using .children.has(char) instead of .children.get(char) to move nodes.

Using '.' instead of '+' for string concatenation.

Using '.' instead of ',' to separate function arguments.

We move to the child node with .children.get(char), concatenate prefix and call collectWords with a comma-separated words array.