Prefix Search Using Trie in DSA Javascript

Mental Model

A trie stores words by sharing common starting letters, making it easy to find all words that start with a given prefix.

Analogy: Imagine a tree where each branch is a letter, and paths from the root to leaves form words. To find words starting with a prefix, you follow the prefix letters down the branches and then list all words below.

root
 ↓
 a -> p -> p -> l -> e [end]
       ↓
       t [end]
 b -> a -> t [end]

Dry Run Walkthrough

Input: Insert words: 'apple', 'app', 'apt', 'bat'; search prefix: 'ap'

Goal: Find all words starting with prefix 'ap'

Step 1: Insert 'apple' letter by letter into trie

root -> a -> p -> p -> l -> e [end]

Why: Build trie nodes for each letter to represent 'apple'

Step 2: Insert 'app' sharing existing nodes for 'a', 'p', 'p', mark end at second 'p'

root -> a -> p -> p [end] -> l -> e [end]

Why: Reuse existing path for prefix, mark word end at 'app'

Step 3: Insert 'apt' sharing 'a', 'p', add new node 't' and mark end

root -> a -> p -> p [end] -> l -> e [end]
                 ↓
                 t [end]

Why: Add new branch for 't' after 'p' to represent 'apt'

Step 4: Insert 'bat' creating new branch from root 'b' -> 'a' -> 't' [end]

root -> a -> p -> p [end] -> l -> e [end]
                 ↓
                 t [end]
  ↓
  b -> a -> t [end]

Why: Add separate branch for word starting with 'b'

Step 5: Search prefix 'ap' by following nodes 'a' then 'p'

root -> a -> p ↑
  branches below: p [end], t [end], l -> e [end]

Why: Locate node representing prefix to find all words below

Step 6: Collect all words below prefix node: 'app', 'apple', 'apt'

Words found: 'app', 'apple', 'apt'

Why: Gather all complete words starting with 'ap'

Result:

Words starting with 'ap': app, apple, apt

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); // advance to child node
    }
    node.isEndOfWord = true; // mark end of word
  }

  searchPrefix(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return null; // prefix not found
      }
      node = node.children.get(char); // advance to next node
    }
    return node; // node at end of prefix
  }

  collectAllWords(node, prefix, words) {
    if (node.isEndOfWord) {
      words.push(prefix); // found a complete word
    }
    for (const [char, childNode] of node.children) {
      this.collectAllWords(childNode, prefix + char, words); // explore deeper
    }
  }

  prefixSearch(prefix) {
    const node = this.searchPrefix(prefix);
    if (!node) return [];
    const words = [];
    this.collectAllWords(node, prefix, words); // gather all words below prefix
    return words;
  }
}

// Driver code
const trie = new Trie();
['apple', 'app', 'apt', 'bat'].forEach(word => trie.insert(word));
const prefix = 'ap';
const results = trie.prefixSearch(prefix);
console.log(`Words starting with '${prefix}': ${results.join(', ')}`);

node = node.children.get(char); // advance to child node

advance node pointer to next letter node

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

mark current node as end of a valid word

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

stop search if prefix letter not found

this.collectAllWords(childNode, prefix + char, words);

recursively collect all words below current node

Output

Words starting with 'ap': app, apple, apt

Complexity Analysis

Time: O(m + k) where m is length of prefix and k is total letters in all matched words because we traverse prefix nodes then collect all words below

Space: O(n) where n is total letters in all inserted words for storing trie nodes

vs Alternative: Compared to scanning all words for prefix match (O(n * m)), trie is faster for repeated prefix searches by avoiding full scans

Edge Cases

Empty prefix string

Returns all words stored in trie

DSA Javascript

if (!node) return [];

Prefix not present in trie

Returns empty list as no words match

DSA Javascript

if (!node) return [];

Prefix is a complete word itself

Includes prefix word plus all longer words starting with it

DSA Javascript

if (node.isEndOfWord) { words.push(prefix); }

When to Use This Pattern

When you need to quickly find all words starting with a prefix in a large set, use a trie because it shares common prefixes and avoids repeated scanning.

Common Mistakes

Mistake: Not marking the end of a word node, causing prefix search to miss complete words
Fix: Set isEndOfWord = true at the last node of each inserted word

Mistake: Returning words without checking if prefix exists, causing errors
Fix: Check if prefix node exists before collecting words, return empty list if not

Summary

Stores words in a tree structure to find all words starting with a prefix efficiently.

Use when you want fast prefix-based search over many words.

The key is sharing nodes for common prefix letters to avoid repeated work.