Autocomplete System with Trie in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting words into a Trie

What is the output of the following code that inserts words into a Trie and then prints the children of the root node?

DSA Javascript

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

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

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

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('dog');
console.log(Object.keys(trie.root.children));

A ['c', 'd']

B ['cat', 'car', 'dog']

C ['c', 'a', 'd']

D ['car', 'dog']

💡 Hint

Look at the first letters of the inserted words and what keys the root node holds.

The root node's children keys are the first letters of the inserted words. Since 'cat' and 'car' start with 'c' and 'dog' starts with 'd', the root children keys are ['c', 'd'].

❓ Predict Output

intermediate

Output of searching a prefix in a Trie

What does the following code print when searching for the prefix 'ca' in the Trie?

DSA Javascript

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

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

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

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

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('dog');
console.log(trie.startsWith('ca'));

A undefined

B false

C true

D TypeError

💡 Hint

Check if the prefix 'ca' exists in the inserted words.

Both 'cat' and 'car' start with 'ca', so the prefix exists in the Trie and the method returns true.

🔧 Debug

advanced

Find the error in the autocomplete function

The following autocomplete function is supposed to return all words in the Trie that start with a given prefix. What error will it cause when run?

DSA Javascript

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

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

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

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

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('dog');
console.log(trie.autocomplete('ca'));

A RangeError: Maximum call stack size exceeded

B TypeError: currentNode.children is undefined

C ReferenceError: dfs is not defined

D No error, outputs ['cat', 'car']

💡 Hint

Check if the dfs function is defined and called correctly.

The dfs function is defined inside autocomplete and called correctly. The code returns ['cat', 'car'] without errors.

❓ Predict Output

advanced

Output of autocomplete with no matching prefix

What is the output of the autocomplete function when searching for prefix 'do' after inserting 'cat', 'car', and 'dog'?

DSA Javascript

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

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

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

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

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('dog');
console.log(trie.autocomplete('do'));

A ['cat', 'car', 'dog']

B ['dog']

C []

D undefined

💡 Hint

Check which inserted words start with 'do'.

'dog' is the only inserted word starting with 'do', so autocomplete returns ['dog'].

🧠 Conceptual

expert

Why use a Trie for Autocomplete?

Which of the following is the best reason to use a Trie data structure for implementing an autocomplete system?

A Tries allow fast prefix searches by sharing common prefixes among words, reducing search time compared to scanning all words.

B Tries use less memory than hash tables because they store only unique words without duplicates.

C Tries automatically sort words alphabetically without extra processing, unlike arrays.

D Tries are easier to implement than arrays or hash tables for storing words.

💡 Hint

Think about how Tries store prefixes and how that helps autocomplete.

Tries store words by their prefixes, allowing quick traversal to all words sharing a prefix, which is efficient for autocomplete.