Prefix Search Using Trie in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. It allows fast retrieval of words by their prefixes.

beginner

How does a Trie help in prefix search?

A Trie stores words by their characters in a tree. Searching for a prefix means following the path of characters in the Trie. If the path exists, all words below that node share the prefix.

intermediate

What is the time complexity of searching a prefix in a Trie?

The time complexity is O(m), where m is the length of the prefix. This is because we only traverse the Trie nodes corresponding to the prefix characters.

beginner

In a Trie node, what does each child represent?

Each child represents a possible next character in the stored words. For example, if the node has a child for 'a', it means some word continues with 'a' from this point.

intermediate

What is the main difference between a Trie and a Hash Map for prefix search?

A Trie supports efficient prefix search by structure, allowing retrieval of all words with a given prefix. A Hash Map does not support prefix search efficiently because it hashes whole keys, not prefixes.

What does each node in a Trie typically store?

A Only a number

B A character and links to child nodes

C A full word string

D A hash of the word

Each Trie node stores a character and links to child nodes representing next characters.

What is the first step to search for a prefix in a Trie?

A Traverse nodes following prefix characters

B Hash the prefix

C Sort all words

D Check the last character only

Searching a prefix means following the path of prefix characters in the Trie.

If a prefix path does not exist in a Trie, what does it mean?

A The prefix is a full word

B All words have that prefix

C The Trie is empty

D No words with that prefix exist

If the path for prefix characters is missing, no stored word has that prefix.

What is the main advantage of using a Trie for prefix search?

A Fast prefix lookup in O(m) time

B Uses less memory than arrays

C Stores numbers efficiently

D Hashes words for quick access

Trie allows prefix search in time proportional to prefix length, which is efficient.

Which of these is NOT true about Tries?

A They can store words sharing prefixes efficiently

B They support prefix search easily

C They hash words for quick lookup

D Each node can have multiple children

Tries do not use hashing; they use tree structure for storing characters.

Explain how a Trie is used to find all words starting with a given prefix.

Think about following characters step-by-step and then exploring below.

Describe the structure of a Trie node and how it supports prefix search.

Focus on what each node holds and how it connects to others.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To efficiently find all words starting with a given prefix

B. To sort words alphabetically

C. To store numbers in ascending order

D. To perform arithmetic operations quickly

Solution

1. Step 1: Understand Trie usage

   A Trie stores words in a tree-like structure where each node represents a character.

2. Step 2: Identify prefix search benefit

   This structure allows quick traversal to find all words sharing a prefix without scanning all words.

3. Final Answer:

   To efficiently find all words starting with a given prefix -> Option A

4. Quick Check:

   Trie = prefix search efficiency [OK]

Hint: Trie nodes represent characters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie stores numbers only
• Assuming Trie is for arithmetic

2. Which of the following is the correct way to initialize an empty Trie node in JavaScript?

easy

A. const node = [];

B. const node = new Map();

C. const node = null;

D. const node = { children: {}, isEnd: false };

Solution

1. Step 1: Understand Trie node structure

   A Trie node typically has a children object to hold next characters and a boolean to mark word end.

2. Step 2: Match correct initialization

   const node = { children: {}, isEnd: false }; correctly creates an object with children as empty object and isEnd as false.

3. Final Answer:

   const node = { children: {}, isEnd: false }; -> Option D

4. Quick Check:

   Trie node = object with children and isEnd [OK]

Hint: Trie nodes use objects with children and end flag [OK]

Common Mistakes:

• Using array instead of object for children
• Setting node to null instead of object
• Using Map without isEnd flag

3. What will be the output of the following code snippet?

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 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'));

medium

A. true

B. false

C. undefined

D. Error

Solution

1. Step 1: Insert words into Trie

   Words 'cat', 'car', and 'dog' are inserted, creating nodes for each character.

2. Step 2: Check prefix 'ca'

   Both 'cat' and 'car' start with 'ca', so traversal finds nodes for 'c' and 'a'.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Prefix 'ca' exists = true [OK]

Hint: If prefix matches inserted words, startsWith returns true [OK]

Common Mistakes:

• Confusing startsWith with exact word search
• Expecting false if prefix is partial
• Ignoring that multiple words share prefix

4. Identify the bug in the following Trie insert method and select the fix:

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;
}

medium

A. Remove node.isEnd assignment

B. Change if condition to check if child does NOT exist before creating new node

C. Initialize node as null before loop

D. Use a Map instead of object for children

Solution

1. Step 1: Analyze insert method logic

   The code creates a new node only if node.children[char] exists, which is incorrect.

2. Step 2: Correct condition for node creation

   We should create a new node only if node.children[char] does NOT exist to avoid overwriting existing nodes.

3. Final Answer:

   Change if condition to check if child does NOT exist before creating new node -> Option B

4. Quick Check:

   Insert new node only if missing [OK]

Hint: Create new child node only if it does not exist [OK]

Common Mistakes:

• Creating new node when child already exists
• Forgetting to mark end of word
• Initializing node incorrectly

5. Given a list of words ['apple', 'app', 'apricot', 'banana'], how would you use a Trie to find all words starting with 'ap'? Choose the correct approach.

hard

A. Insert only words starting with 'ap' into Trie and ignore others

B. Sort the list and filter words starting with 'ap' using string methods

C. Insert all words into Trie, then traverse nodes for prefix 'ap' and collect all descendant words

D. Use a hash map to store words and check prefix by substring matching

Solution

1. Step 1: Build Trie with all words

   Insert all words so the Trie contains complete data for prefix search.

2. Step 2: Traverse Trie for prefix 'ap'

   Navigate nodes for 'a' then 'p', then collect all words from this subtree.

3. Step 3: Collect descendant words

   Gather words like 'apple', 'app', and 'apricot' that share the prefix.

4. Final Answer:

   Insert all words into Trie, then traverse nodes for prefix 'ap' and collect all descendant words -> Option C

5. Quick Check:

   Trie + prefix traversal = all matching words [OK]

Hint: Insert all words, then traverse prefix subtree to find matches [OK]

Common Mistakes:

• Filtering list without Trie defeats purpose
• Ignoring words not starting with prefix during insertion
• Using hash map instead of Trie for prefix search