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.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To efficiently find all words starting with a given prefix

B. To sort words alphabetically

C. To store numbers in ascending order

D. To perform arithmetic operations quickly

Solution

1. Step 1: Understand Trie usage

   A Trie stores words in a tree-like structure where each node represents a character.

2. Step 2: Identify prefix search benefit

   This structure allows quick traversal to find all words sharing a prefix without scanning all words.

3. Final Answer:

   To efficiently find all words starting with a given prefix -> Option A

4. Quick Check:

   Trie = prefix search efficiency [OK]

Hint: Trie nodes represent characters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie stores numbers only
• Assuming Trie is for arithmetic

2. Which of the following is the correct way to initialize an empty Trie node in JavaScript?

easy

A. const node = [];

B. const node = new Map();

C. const node = null;

D. const node = { children: {}, isEnd: false };

Solution

1. Step 1: Understand Trie node structure

   A Trie node typically has a children object to hold next characters and a boolean to mark word end.

2. Step 2: Match correct initialization

   const node = { children: {}, isEnd: false }; correctly creates an object with children as empty object and isEnd as false.

3. Final Answer:

   const node = { children: {}, isEnd: false }; -> Option D

4. Quick Check:

   Trie node = object with children and isEnd [OK]

Hint: Trie nodes use objects with children and end flag [OK]

Common Mistakes:

• Using array instead of object for children
• Setting node to null instead of object
• Using Map without isEnd flag

3. What will be the output of the following 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;
  }
  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true;
  }
}

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

medium

A. true

B. false

C. undefined

D. Error

Solution

1. Step 1: Insert words into Trie

   Words 'cat', 'car', and 'dog' are inserted, creating nodes for each character.

2. Step 2: Check prefix 'ca'

   Both 'cat' and 'car' start with 'ca', so traversal finds nodes for 'c' and 'a'.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Prefix 'ca' exists = true [OK]

Hint: If prefix matches inserted words, startsWith returns true [OK]

Common Mistakes:

• Confusing startsWith with exact word search
• Expecting false if prefix is partial
• Ignoring that multiple words share prefix

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

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;
}

medium

A. Remove node.isEnd assignment

B. Change if condition to check if child does NOT exist before creating new node

C. Initialize node as null before loop

D. Use a Map instead of object for children

Solution

1. Step 1: Analyze insert method logic

   The code creates a new node only if node.children[char] exists, which is incorrect.

2. Step 2: Correct condition for node creation

   We should create a new node only if node.children[char] does NOT exist to avoid overwriting existing nodes.

3. Final Answer:

   Change if condition to check if child does NOT exist before creating new node -> Option B

4. Quick Check:

   Insert new node only if missing [OK]

Hint: Create new child node only if it does not exist [OK]

Common Mistakes:

• Creating new node when child already exists
• Forgetting to mark end of word
• Initializing node incorrectly

5. Given a list of words ['apple', 'app', 'apricot', 'banana'], how would you use a Trie to find all words starting with 'ap'? Choose the correct approach.

hard

A. Insert only words starting with 'ap' into Trie and ignore others

B. Sort the list and filter words starting with 'ap' using string methods

C. Insert all words into Trie, then traverse nodes for prefix 'ap' and collect all descendant words

D. Use a hash map to store words and check prefix by substring matching

Solution

1. Step 1: Build Trie with all words

   Insert all words so the Trie contains complete data for prefix search.

2. Step 2: Traverse Trie for prefix 'ap'

   Navigate nodes for 'a' then 'p', then collect all words from this subtree.

3. Step 3: Collect descendant words

   Gather words like 'apple', 'app', and 'apricot' that share the prefix.

4. Final Answer:

   Insert all words into Trie, then traverse nodes for prefix 'ap' and collect all descendant words -> Option C

5. Quick Check:

   Trie + prefix traversal = all matching words [OK]

Hint: Insert all words, then traverse prefix subtree to find matches [OK]

Common Mistakes:

• Filtering list without Trie defeats purpose
• Ignoring words not starting with prefix during insertion
• Using hash map instead of Trie for prefix search