Prefix Search Using Trie in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new Trie node with an empty children object.

DSA Javascript

class TrieNode {
  constructor() {
    this.children = [1];
    this.isEndOfWord = false;
  }
}

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

A{}

B[]

C''

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using an array instead of an object for children.

We use an empty object {} to store children nodes by character keys.

2fill in blank

medium

Complete the code to insert a character into the Trie children if it does not exist.

DSA Javascript

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

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

Achar

Bword

Cnode

Dthis

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole word or node instead of the current character.

We move to the child node corresponding to the current character char.

3fill in blank

hard

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

DSA Javascript

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

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

Aprefix

Bnode

Cchar

Dthis

Attempts:

3 left

💡 Hint

Common Mistakes

Checking children with the whole prefix or wrong variable.

We check if the current character char exists in the children of the current node.

4fill in blank

hard

Fill both blanks to complete the method that returns all words starting with a given prefix.

DSA Javascript

startsWith(prefix) {
  let node = this.root;
  for (let char of prefix) {
    if (!node.children[[1]]) {
      return [];
    }
    node = node.children[[2]];
  }
  const results = [];
  function dfs(currentNode, path) {
    if (currentNode.isEndOfWord) {
      results.push(path);
    }
    for (let key in currentNode.children) {
      dfs(currentNode.children[key], path + key);
    }
  }
  dfs(node, prefix);
  return results;
}

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

Achar

Bprefix

Cnode

Dthis

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables or the whole prefix instead of char.

Both blanks use char to access the child node for each character in the prefix.

5fill in blank

hard

Fill both blanks to complete the method that collects words from a Trie node using DFS.

DSA Javascript

collectWords(node, path, words) {
  if (node.isEndOfWord) {
    words.push([1]);
  }
  for (let char in node.children) {
    this.collectWords(node.children[char], [2], words);
  }
}

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

Apath

Bpath + char

Cwords

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing the wrong variable or not extending the path correctly.

We add the current path to words when a word ends, and extend the path with char when going deeper.