Prefix Search Using Trie in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Result

What is the output of the following code that inserts words into a Trie and searches for words with prefix 'app'?

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = 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.isEnd = true;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) {
        return [];
      }
      node = node.children[char];
    }
    const results = [];
    const dfs = (currNode, path) => {
      if (currNode.isEnd) results.push(path);
      for (const c in currNode.children) {
        dfs(currNode.children[c], path + c);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

const trie = new Trie();
['apple', 'app', 'application', 'bat', 'ball'].forEach(w => trie.insert(w));
console.log(trie.startsWith('app'));

A ["app", "apple", "application"]

B ["apple", "application"]

C ["app", "application"]

D ["bat", "ball"]

💡 Hint

Think about all words starting exactly with 'app' including the prefix itself.

The Trie stores all words. The startsWith method finds all words starting with 'app'. The words 'app', 'apple', and 'application' start with 'app'.

🧠 Conceptual

intermediate

Number of Nodes in Trie After Insertions

After inserting the words ['cat', 'car', 'cart', 'dog'] into an empty Trie, how many nodes does the Trie contain?

A 8

B 10

C 7

D 9

💡 Hint

Count shared prefixes only once.

The words share prefixes: 'ca' is shared by 'cat', 'car', 'cart'. Counting nodes: root + c + a + t + r + t + d + o + g = 9 nodes.

🔧 Debug

advanced

Identify the Error in Trie Search Method

What error does the following Trie search method produce when searching for a prefix that does not exist?

DSA Javascript

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

A SyntaxError due to missing return statement

B Returns false correctly

C TypeError: Cannot read property 'children' of undefined

D Always returns true

💡 Hint

What happens if node.children[char] is undefined and you try to access its children?

If prefix character is missing, node.children[char] is undefined. Next loop tries to access children of undefined causing TypeError.

🚀 Application

advanced

Find All Words with Prefix in Trie

Given a Trie with words inserted, which method correctly returns all words starting with a given prefix?

A Traverse to prefix node, then DFS to collect all words from there

B Return all words in Trie and filter those starting with prefix

C Check only if prefix is a word in Trie and return it

D Return empty list if prefix length is less than 3

💡 Hint

Think about efficient search using Trie structure.

The efficient way is to find the node representing prefix, then explore all descendants to get words starting with prefix.

❓ Predict Output

expert

Output of Complex Trie Prefix Search

What is the output of the following code snippet?

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = 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.isEnd = true;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return [];
      node = node.children[char];
    }
    const results = [];
    const dfs = (currNode, path) => {
      if (currNode.isEnd) results.push(path);
      for (const c in currNode.children) {
        dfs(currNode.children[c], path + c);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

const trie = new Trie();
['team', 'teach', 'test', 'tester', 'testing'].forEach(w => trie.insert(w));
console.log(trie.startsWith('te'));

A ["tester", "testing"]

B ["team", "teach", "test", "tester", "testing"]

C ["team", "teach"]

D ["test", "tester", "testing"]

💡 Hint

All words starting with 'te' should be included.

All inserted words start with 'te', so all are returned in lexicographical order of DFS traversal.