Word Search in Trie in DSA Javascript

Mental Model

A trie stores words by sharing common letters in a tree. Searching means following letters down the branches.

Analogy: Imagine a tree where each branch is a letter. To find a word, you walk down the branches matching each letter in order.

root
 ↓
  t -> e -> a
        ↑
      curr

Dry Run Walkthrough

Input: Trie with words: 'to', 'tea', 'ted', 'ten', search for 'tea'

Goal: Find if the word 'tea' exists in the trie

Step 1: Start at root, look for 't'

root -> [t] -> e -> a

Why: First letter 't' must be found among root's children

Step 2: Move to node 't', look for 'e'

root -> t -> [e] -> a -> null

Why: Second letter 'e' must be found among 't' node's children

Step 3: Move to node 'e', look for 'a'

root -> t -> e -> [a] -> null

Why: Third letter 'a' must be found among 'e' node's children

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

root -> t -> e -> a* (end)

Why: Confirm the word ends here to ensure full match

Result:

root -> t -> e -> a* (end)
Word 'tea' found: true

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); // move down the trie
    }
    node.isEndOfWord = true; // mark end of word
  }

  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 down the trie
    }
    return node.isEndOfWord; // true if word ends here
  }
}

// Driver code
const trie = new Trie();
['to', 'tea', 'ted', 'ten'].forEach(word => trie.insert(word));
console.log(trie.search('tea'));

node = node.children.get(char); // move down the trie

advance node pointer to child matching current letter

node.isEndOfWord = true; // mark end of word

mark current node as end of a valid word

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

stop search early if letter missing in children

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

confirm full word match by checking end marker

Output

true

Complexity Analysis

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

Space: O(n*m) where n is number of words and m average length, for storing trie nodes

vs Alternative: Compared to searching a list of words (O(n*m)), trie search is faster (O(m)) by direct letter traversal

Edge Cases

searching empty string

returns false because empty word is not stored

DSA Javascript

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

searching word not in trie

returns false early when letter missing

DSA Javascript

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

searching prefix of a word but not a full word

returns false because end marker is missing

DSA Javascript

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

When to Use This Pattern

When you need to quickly check if words or prefixes exist in a large set, use a trie search pattern because it follows letters step-by-step efficiently.

Common Mistakes

Mistake: Not checking if the node marks the end of a word after traversal
Fix: Always check the isEndOfWord flag to confirm full word match

Mistake: Trying to access children without checking if the letter exists
Fix: Check if children has the letter before moving down to avoid errors

Summary

It checks if a word exists by following letters down a tree of shared prefixes.

Use it when you want fast word lookups among many stored words.

The key is to move letter by letter and confirm the word ends exactly at the last letter.