Autocomplete System with Trie in DSA Javascript

Mental Model

A trie stores words by sharing common prefixes, so we can quickly find all words starting with a given prefix.

Analogy: Imagine a tree of roads where each road sign is a letter. To find all places starting with 'ca', you follow the roads for 'c' then 'a' and see all destinations branching from there.

root
 ↓
 c -> a -> t (word end)
       ↓
       r -> null

Each arrow is a letter link; nodes mark letters; some nodes mark word ends.

Dry Run Walkthrough

Input: Insert words: 'cat', 'car', 'cart', then autocomplete prefix 'ca'

Goal: Build trie with words and find all words starting with 'ca'

Step 1: Insert 'cat' letter by letter

root -> c -> a -> t* -> null

Why: Create path for 'cat' marking 't' as word end

Step 2: Insert 'car' sharing prefix 'ca'

root -> c -> a -> t* -> null
                 ↓
                 r* -> null

Why: Reuse 'c' and 'a', add new branch 'r' marked as word end

Step 3: Insert 'cart' extending from 'car'

root -> c -> a -> t* -> null
                 ↓
                 r* -> t* -> null

Why: Add 't' after 'r' marking new word end for 'cart'

Step 4: Autocomplete prefix 'ca' by traversing trie

At node 'a' under 'c', collect words: 'cat', 'car', 'cart'

Why: All words starting with 'ca' are under this node

Result:

root -> c -> a -> t* -> null
                 ↓
                 r* -> t* -> null
Autocomplete results: ['cat', 'car', 'cart']

Annotated Code

DSA Javascript

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isWord = 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 node to child
    }
    node.isWord = true; // mark end of word
  }

  _dfs(node, prefix, results) {
    if (node.isWord) {
      results.push(prefix); // found a word
    }
    for (const [char, child] of node.children) {
      this._dfs(child, prefix + char, results); // explore deeper
    }
  }

  autocomplete(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return []; // prefix not found
      }
      node = node.children.get(char); // move to prefix node
    }
    const results = [];
    this._dfs(node, prefix, results); // collect all words
    return results;
  }
}

// Driver code
const trie = new Trie();
['cat', 'car', 'cart'].forEach(word => trie.insert(word));
const completions = trie.autocomplete('ca');
console.log(completions.join(', '));

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

advance node to next letter node to build path

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

mark current node as a complete word

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

stop if prefix path missing, no completions

this._dfs(node, prefix, results); // collect all words

collect all words starting from prefix node

if (node.isWord) { results.push(prefix); }

add word to results when word end found

Output

cat, car, cart

Complexity Analysis

Time: O(m + n) where m is prefix length and n is total letters in matched words because we traverse prefix then collect all completions

Space: O(n) for storing all inserted words in trie nodes

vs Alternative: Compared to scanning all words linearly (O(k * w) where k is prefix length and w is number of words), trie is faster for autocomplete by avoiding full scans

Edge Cases

Empty prefix

Returns all words stored in trie

DSA Javascript

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

Prefix not in trie

Returns empty list immediately

DSA Javascript

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

Words with shared prefixes

Trie branches correctly share nodes without duplication

DSA Javascript

if (!node.children.has(char)) { node.children.set(char, new TrieNode()); }

When to Use This Pattern

When you need to quickly find all words starting with a prefix, use a trie because it organizes words by shared prefixes for fast lookup.

Common Mistakes

Mistake: Not marking the end of a word, so autocomplete returns incomplete results
Fix: Set isWord = true at the last node of each inserted word

Mistake: Not checking if prefix exists before DFS, causing errors or wrong results
Fix: Return empty list if prefix path is missing before collecting completions

Summary

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

Use when you want fast autocomplete suggestions from a large word list.

The key is sharing prefix nodes so you only explore relevant branches for the prefix.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To efficiently store and search prefixes of words

B. To sort words alphabetically

C. To count the frequency of words

D. To encrypt the stored words

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie is a tree-like data structure designed to store strings by their prefixes, allowing quick prefix-based searches.

2. Step 2: Relate Trie to autocomplete functionality

   Autocomplete needs to find all words starting with a given prefix efficiently, which Trie supports by traversing nodes matching the prefix.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is built for prefix matching, perfect for autocomplete [OK]

Common Mistakes:

• Confusing Trie with sorting data structure
• Thinking Trie encrypts data
• Assuming Trie counts word frequency only

2. Which of the following is the correct way to insert a word "cat" into a Trie node in JavaScript?

easy

A. node.children.push('c');

B. node.children['c'] = new TrieNode();

C. node['c'] = 'cat';

D. node.add('cat');

Solution

1. Step 1: Understand Trie node structure

   Each Trie node has a children object mapping characters to child nodes, so to insert 'c', we assign a new TrieNode to node.children['c'].

2. Step 2: Check each option's correctness

   node.children['c'] = new TrieNode(); correctly assigns a new TrieNode to the character key. Options B, C, and D do not follow the standard Trie insertion method.

3. Final Answer:

   node.children['c'] = new TrieNode(); -> Option B

4. Quick Check:

   Insert char by assigning new TrieNode in children map [OK]

Hint: Use children map with character keys for Trie insertion [OK]

Common Mistakes:

• Using array push instead of map assignment
• Assigning string instead of TrieNode
• Calling undefined add method

3. Given the following code snippet for searching words with prefix "app" in a Trie, what will be the output?

const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("application");
const results = trie.searchPrefix("app");
console.log(results);

medium

A. ["apple", "application"]

B. ["app"]

C. []

D. ["apple", "app", "application"]

Solution

1. Step 1: Insert words into Trie

   Words "apple", "app", and "application" are inserted, so all prefixes starting with "app" exist in the Trie.

2. Step 2: Search for prefix "app"

   The searchPrefix method returns all words starting with "app", which includes all three inserted words.

3. Final Answer:

   ["apple", "app", "application"] -> Option D

4. Quick Check:

   All words with prefix "app" returned [OK]

Hint: Search prefix returns all words starting with it [OK]

Common Mistakes:

• Expecting only exact matches
• Ignoring shorter word "app" itself
• Assuming empty result if prefix is a word

4. The following code tries to insert words into a Trie but throws an error. What is the bug?

class TrieNode {
  constructor() {
    this.children = [];
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEnd = true;
  }
}

const trie = new Trie();
trie.insert("dog");

medium

A. children should be an object, not an array

B. isEnd should be initialized to true

C. Missing return statement in insert method

D. for loop should use index instead of for-of

Solution

1. Step 1: Analyze children data structure

   children is initialized as an empty array, but characters are used as keys, which are strings, not numeric indices.

2. Step 2: Identify correct data structure for children

   children should be an object (map) to use string keys like 'd', 'o', 'g'. Using array causes undefined behavior and errors.

3. Final Answer:

   children should be an object, not an array -> Option A

4. Quick Check:

   Use object for children keys [OK]

Hint: Use object for children to map chars, not array [OK]

Common Mistakes:

• Using array for children with string keys
• Setting isEnd incorrectly
• Thinking loop type causes error

5. You want to build an autocomplete system that returns the top 2 most frequent words starting with a prefix. Which modification to a Trie node helps achieve this efficiently?

hard

A. Use an array instead of object for children

B. Store only the full words at leaf nodes

C. Store a frequency count and maintain a sorted list of top words at each node

D. Store the entire dictionary at each node

Solution

1. Step 1: Understand requirement for top frequent words

   To quickly return top 2 frequent words for any prefix, each node should track frequency info and top words under it.

2. Step 2: Choose data structure modification

   Storing frequency counts and maintaining a sorted list of top words at each node allows fast retrieval without full traversal.

3. Final Answer:

   Store a frequency count and maintain a sorted list of top words at each node -> Option C

4. Quick Check:

   Frequency + top words per node = efficient autocomplete [OK]

Hint: Keep top words and frequencies at nodes for fast autocomplete [OK]

Common Mistakes:

• Storing full dictionary at each node wastes memory
• Using arrays for children slows lookup
• Ignoring frequency info for ranking