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.