Trie Search Operation in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Search for Existing Word

What is the output of the following TypeScript code that inserts words into a Trie and searches for the word 'cat'?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

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

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

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

A TypeError

B false

C undefined

D true

💡 Hint

Think about whether the word 'cat' was inserted before searching.

The word 'cat' was inserted into the Trie, so searching for it returns true.

❓ Predict Output

intermediate

Output of Trie Search for Non-Existing Word

What is the output of the following TypeScript code that inserts words into a Trie and searches for the word 'bat'?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

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

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

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

A undefined

B true

C false

D ReferenceError

💡 Hint

Check if 'bat' was inserted before searching.

The word 'bat' was not inserted into the Trie, so searching for it returns false.

🧠 Conceptual

advanced

Understanding Trie Search Behavior

In a Trie, what does it mean if the search for a word returns false even though all characters of the word are present in the Trie nodes?

A The word is a prefix but not a complete word stored in the Trie

B The Trie is empty and has no words stored

C The search function has a bug and always returns false

D The word is stored but the search function only checks prefixes

💡 Hint

Think about the difference between a prefix and a complete word in a Trie.

If all characters are found but the isEndOfWord flag is false, it means the searched word is only a prefix, not a full word stored in the Trie.

❓ Predict Output

advanced

Output of Trie Search After Partial Insertions

What is the output of the following TypeScript code that inserts 'car' and 'cart' into a Trie and searches for 'car' and 'cart'?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

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

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

const trie = new Trie();
trie.insert('car');
trie.insert('cart');
console.log(trie.search('car'));
console.log(trie.search('cart'));

A true false

B true true

C false true

D false false

💡 Hint

Both 'car' and 'cart' were inserted, so both searches should succeed.

Both words 'car' and 'cart' were inserted, so searching for either returns true.

🔧 Debug

expert

Identify the Bug in Trie Search Implementation

What error will the following TypeScript code produce when searching for the word 'bat' after inserting 'bat' and 'bath' into the Trie?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

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

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

const trie = new Trie();
trie.insert('bat');
trie.insert('bath');
console.log(trie.search('bat'));
console.log(trie.search('bath'));
console.log(trie.search('batman'));

A false

B true

C TypeError

D undefined

💡 Hint

Consider what happens when searching for a word that is not inserted but shares a prefix.

Searching for 'batman' returns false because the prefix 'bat' exists but 'batman' was not inserted.

Practice

1. What does the search operation in a Trie data structure do?

easy

A. Checks if a given word exists in the Trie

B. Deletes a word from the Trie

C. Inserts a new word into the Trie

D. Counts the total words stored in the Trie

Solution

1. Step 1: Understand the purpose of search in Trie

   The search operation is designed to check if a specific word is present in the Trie data structure.

2. Step 2: Differentiate from other operations

   Insertion adds words, deletion removes words, and counting totals words, but search only checks existence.

3. Final Answer:

   Checks if a given word exists in the Trie -> Option A

4. Quick Check:

   Search = Check existence [OK]

Hint: Search checks presence of word, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert operation
• Thinking search deletes words
• Assuming search counts words

2. Which of the following is the correct TypeScript method signature for a Trie search function that returns a boolean?

easy

A. search(word: boolean): boolean

B. search(word: number): string

C. search(word: string): void

D. search(word: string): boolean

Solution

1. Step 1: Identify input and output types for search

   The search method takes a word as a string and returns true or false, so input is string and output is boolean.

2. Step 2: Match method signature with correct types

   Only search(word: string): boolean matches the expected input and output types.

3. Final Answer:

   search(word: string): boolean -> Option D

4. Quick Check:

   Input string, output boolean [OK]

Hint: Search takes string, returns true/false [OK]

Common Mistakes:

• Using wrong input type like number or boolean
• Returning void instead of boolean
• Confusing return type with string

3. Given the following TypeScript Trie search code, what will be the output?

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

medium

A. true\ntrue

B. true\nfalse

C. false\ntrue

D. false\nfalse

Solution

1. Step 1: Check inserted words in Trie

   The words 'cat', 'car', and 'dog' are inserted into the Trie.

2. Step 2: Search for 'car' and 'cap'

   'car' exists in the Trie, so search returns true. 'cap' was not inserted, so search returns false.

3. Final Answer:

   true\nfalse -> Option B

4. Quick Check:

   Inserted words found, missing words not found [OK]

Hint: Inserted words return true, others false [OK]

Common Mistakes:

• Assuming 'cap' is found because it starts like 'car'
• Mixing true/false order in output
• Forgetting to insert words before search

4. Identify the bug in this TypeScript Trie search method:

search(word: string): boolean {
  let node = this.root;
  for (let i = 0; i <= word.length; i++) {
    const char = word[i];
    if (!node.children.has(char)) return false;
    node = node.children.get(char)!;
  }
  return node.isEndOfWord;
}

medium

A. Loop condition should be i < word.length, not <=

B. Missing check for empty string input

C. Should return true before loop ends

D. Incorrect use of non-null assertion operator (!)

Solution

1. Step 1: Analyze loop boundary in search method

   The loop runs from i = 0 to i <= word.length, which means it accesses word[word.length], an undefined index.

2. Step 2: Correct loop condition to avoid out-of-bounds

   The loop should run while i < word.length to access valid characters only.

3. Final Answer:

   Loop condition should be i < word.length, not <= -> Option A

4. Quick Check:

   Loop boundary off by one [OK]

Hint: Loop over characters with i < length, not <= length [OK]

Common Mistakes:

• Using <= causes undefined access
• Ignoring empty string edge case
• Misusing non-null assertion without checks

5. You want to modify a Trie search method to support prefix search (check if any word starts with given prefix). Which change is correct?

hard

A. Return true only if prefix is a complete word (isEndOfWord true)

B. Return false if prefix length is less than 3 characters

C. Return true as soon as all prefix characters are found, without checking isEndOfWord

D. Return true only if prefix matches exactly one word

Solution

1. Step 1: Understand prefix search goal

   Prefix search should confirm if any word starts with the given prefix, not necessarily a complete word.

2. Step 2: Adjust search logic for prefix

   Return true once all prefix characters are found in sequence, without requiring isEndOfWord to be true.

3. Final Answer:

   Return true as soon as all prefix characters are found, without checking isEndOfWord -> Option C

4. Quick Check:

   Prefix found means true, no full word check needed [OK]

Hint: Prefix search stops after matching prefix, ignores full word flag [OK]

Common Mistakes:

• Checking isEndOfWord for prefix search
• Rejecting short prefixes arbitrarily
• Requiring prefix to match exactly one word