Trie Search Operation in DSA Javascript

Mental Model

A trie stores words by branching letters step-by-step. Searching means following these branches letter by letter to find if a word exists.

Analogy: Imagine a tree of roads where each road sign is a letter. To find a word, you follow the signs one by one until you reach the end of the word or get lost.

root
 ↓
 a -> b -> c (end)
 ↓
 d -> e (end)

Each arrow is a letter link. 'end' marks a complete word.

Dry Run Walkthrough

Input: Trie with words: 'cat', 'car', 'dog'. Search for 'car'.

Goal: Check if 'car' exists in the trie by following letters c -> a -> r.

Step 1: Start at root node, look for child 'c'

root -> [c] -> a -> t (end), r (end)
root -> d -> o -> g (end)

Why: We must find the first letter 'c' to continue searching the word.

Step 2: Move to node 'c', look for child 'a'

root -> c -> [a] -> t (end), r (end)
root -> d -> o -> g (end)

Why: Next letter 'a' must be found under 'c' to continue.

Step 3: Move to node 'a', look for child 'r'

root -> c -> a -> [r] (end), t (end)
root -> d -> o -> g (end)

Why: Next letter 'r' must be found under 'a' to complete the word.

Step 4: Check if node 'r' marks end of a word

root -> c -> a -> r (end), t (end)
root -> d -> o -> g (end)

Why: If 'r' node marks end, 'car' exists in trie.

Result:

root -> c -> a -> r (end), t (end)
root -> d -> o -> g (end)
Answer: 'car' found

Annotated Code

DSA Javascript

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

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

  insert(word) {
    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) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return false; // letter missing, word not found
      }
      node = node.children.get(char); // move to next letter node
    }
    return node.isEndOfWord; // check if word ends here
  }
}

// Driver code
const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('dog');

const wordToSearch = 'car';
const found = trie.search(wordToSearch);
console.log(found ? `'${wordToSearch}' found` : `'${wordToSearch}' not found`);

if (!node.children.has(char)) {

Check if current letter exists as child node

node = node.children.get(char);

Advance to child node for next letter

return false; // letter missing, word not found

Stop search early if letter missing

return node.isEndOfWord; // check if word ends here

Confirm word ends exactly at last letter node

Output

'car' found

Complexity Analysis

Time: O(m) because we check each of the m letters in the search word once

Space: O(1) extra space during search since we only use pointers, no extra storage

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster as it avoids scanning all words

Edge Cases

Search for empty string

Returns false because empty word is not stored

DSA Javascript

return node.isEndOfWord; // check if word ends here

Search for word not inserted

Returns false when a letter is missing in trie

DSA Javascript

if (!node.children.has(char)) { return false; }

Search for prefix of a word but not a full word

Returns false if prefix node is not marked as end

DSA Javascript

return node.isEndOfWord; // check if word ends here

When to Use This Pattern

When you need to quickly check if a word or prefix exists in a set of strings, use trie search to follow letter branches efficiently.

Common Mistakes

Mistake: Not checking if the last node marks the end of a word, causing false positives on prefixes
Fix: Always check node.isEndOfWord after traversing all letters

Mistake: Trying to access child nodes without checking if they exist, causing errors
Fix: Check if child exists with has() before getting it

Summary

It checks if a word exists by following letter nodes step-by-step in the trie.

Use it when you want fast word lookups in a large set of strings.

The key is to move letter by letter and confirm the last letter marks a complete word.

Practice

1. What does the search operation in a Trie data structure primarily check for?

easy

A. The length of the longest word in the Trie

B. If the Trie is empty

C. If a given word exists in the Trie

D. The number of words stored in the Trie

Solution

1. Step 1: Understand the purpose of Trie search

   The search operation in a Trie is designed to check if a specific word is present in the Trie by traversing nodes corresponding to each character.

2. Step 2: Identify what the search confirms

   It confirms the presence or absence of the entire word, not the count or length of words stored.

3. Final Answer:

   If a given word exists in the Trie -> Option C

4. Quick Check:

   Trie search checks word existence [OK]

Hint: Search checks full word presence in Trie nodes [OK]

Common Mistakes:

• Confusing search with counting words
• Thinking search returns word length
• Assuming search checks if Trie is empty

2. Which of the following is the correct way to check if a character node exists in a Trie during search in JavaScript?

easy

A. if (node.char !== null)

B. if (node[char] !== undefined)

C. if (node.has(char))

D. if (node.char === true)

Solution

1. Step 1: Understand Trie node structure in JavaScript

   Trie nodes are usually objects where keys are characters. Checking if a character exists uses property access and undefined check.

2. Step 2: Identify correct syntax for existence check

   Using node[char] !== undefined correctly checks if the character key exists in the node object.

3. Final Answer:

   if (node[char] !== undefined) -> Option B

4. Quick Check:

   Check node property with !== undefined [OK]

Hint: Use node[char] !== undefined to check character node [OK]

Common Mistakes:

• Using dot notation with variable char
• Using incorrect method like has() on object
• Checking for null instead of undefined

3. What will be the output of the following JavaScript 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;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEnd;
  }
}

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

medium

A. true false

B. false true

C. true true

D. false false

Solution

1. Step 1: Insert words 'cat' and 'car' into Trie

   Both words are inserted by creating nodes for each character and marking the last node's isEnd as true.

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

   'cat' exists fully with isEnd true, so search returns true. 'cap' is missing 'p' node, so search returns false.

3. Final Answer:

   true false -> Option A

4. Quick Check:

   Search 'cat' = true, 'cap' = false [OK]

Hint: Search returns true only if full word and isEnd true [OK]

Common Mistakes:

• Assuming partial matches return true
• Not setting isEnd flag on insert
• Confusing children object access

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

search(word) {
  let node = this.root;
  for (const char of word) {
    if (node.children[char] === undefined) return false;
    node = node.children[char];
  }
  return true;
}

medium

A. Use 'for (let i=0; i

B. Change '===' to '!==' in the if condition

C. Initialize node with a new TrieNode inside the method

D. Return node.isEnd instead of true at the end

Solution

1. Step 1: Analyze the search method's return value

   The method returns true after traversing all characters without checking if the last node marks the end of a word.

2. Step 2: Correct the return to check word completion

   Return node.isEnd to confirm the word ends here, not just prefix exists.

3. Final Answer:

   Return node.isEnd instead of true at the end -> Option D

4. Quick Check:

   Check isEnd flag to confirm full word [OK]

Hint: Always check isEnd flag after traversal [OK]

Common Mistakes:

• Returning true without isEnd check
• Changing comparison operator incorrectly
• Unnecessary loop syntax changes

5. Given a Trie containing the words ['apple', 'app', 'bat', 'bath'], which of the following search queries will return true? Assume the search method correctly checks for full word presence. Select the correct combination.

hard

A. search('app'), search('bat'), search('bath')

B. search('appl'), search('bat'), search('bath')

C. search('apple'), search('bat'), search('batman')

D. search('app'), search('bath'), search('batman')

Solution

1. Step 1: Identify words present in the Trie

   The Trie contains 'apple', 'app', 'bat', and 'bath'. Only these exact words return true on search.

2. Step 2: Check each option's search queries

   search('app'), search('bat'), search('bath') searches 'app', 'bat', 'bath' all present. Others include partial or missing words like 'appl' or 'batman' which return false.

3. Final Answer:

   search('app'), search('bat'), search('bath') -> Option A

4. Quick Check:

   Only full words in Trie return true [OK]

Hint: Search true only for full words inserted in Trie [OK]

Common Mistakes:

• Assuming partial words return true
• Confusing prefixes with full words
• Including words not inserted in Trie