Autocomplete System with Trie in DSA Javascript - Build from Scratch

Autocomplete System with Trie

📖 Scenario: You are building a simple autocomplete system like the ones used in search engines or messaging apps. When a user types some letters, the system suggests words that start with those letters.To do this efficiently, you will use a Trie data structure, which stores words in a tree-like format where each node represents a letter.

🎯 Goal: Build a Trie to store a list of words and then find all words that start with a given prefix.This will help you understand how autocomplete systems work behind the scenes.

📋 What You'll Learn

Create a TrieNode class with children and end-of-word marker

Create a Trie class with insert and searchPrefix methods

Insert given words into the Trie

Find all words starting with a given prefix

Print the list of autocomplete suggestions

💡 Why This Matters

🌍 Real World

Autocomplete systems help users find words or commands quickly by suggesting possible completions as they type, improving user experience in search engines, messaging apps, and code editors.

💼 Career

Understanding Tries and autocomplete logic is useful for software engineers working on search features, text input optimization, and user interface improvements.

1

Create TrieNode and Trie classes

Create a class called TrieNode with a constructor that initializes children as an empty object and isEndOfWord as false. Then create a class called Trie with a constructor that initializes root as a new TrieNode.

DSA Javascript

# Your code here

Hint

Think of TrieNode as a box holding letters and a flag to mark if a word ends there. The Trie has a root node to start from.

2

Add insert method to Trie

Add a method called insert to the Trie class that takes a word string. Use a for loop with variable char to go through each character in word. For each char, if it does not exist in currentNode.children, create a new TrieNode. Move currentNode to the child node for char. After the loop, set currentNode.isEndOfWord to true.

DSA Javascript

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // Add insert method below
    
    // Your code here
}

Hint

Insert each letter one by one. If the letter path does not exist, create it. Mark the end of the word at the last letter.

3

Add searchPrefix method to find all words with a prefix

Add a method called searchPrefix to the Trie class that takes a prefix string. Use a for loop with variable char to traverse the Trie nodes for each character in prefix. If at any point char is not found in currentNode.children, return an empty array. Then create a helper function dfs inside searchPrefix that takes a node and path string. If node.isEndOfWord is true, add path to a results array. Recursively call dfs for each child character. Finally, call dfs starting from the node at the end of the prefix and return the results array.

DSA Javascript

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let currentNode = this.root;
        for (const char of word) {
            if (!currentNode.children[char]) {
                currentNode.children[char] = new TrieNode();
            }
            currentNode = currentNode.children[char];
        }
        currentNode.isEndOfWord = true;
    }

    // Add searchPrefix method below
    
    // Your code here
}

Hint

First find the node matching the prefix. Then explore all paths from there to find complete words.

4

Insert words and print autocomplete suggestions

Create a Trie instance called trie. Insert the words 'apple', 'app', 'application', 'bat', and 'ball' into trie using the insert method. Then call trie.searchPrefix('app') and print the result using console.log.

DSA Javascript

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let currentNode = this.root;
        for (const char of word) {
            if (!currentNode.children[char]) {
                currentNode.children[char] = new TrieNode();
            }
            currentNode = currentNode.children[char];
        }
        currentNode.isEndOfWord = true;
    }

    searchPrefix(prefix) {
        let currentNode = this.root;
        for (const char of prefix) {
            if (!currentNode.children[char]) {
                return [];
            }
            currentNode = currentNode.children[char];
        }

        const results = [];

        function dfs(node, path) {
            if (node.isEndOfWord) {
                results.push(path);
            }
            for (const childChar in node.children) {
                dfs(node.children[childChar], path + childChar);
            }
        }

        dfs(currentNode, prefix);
        return results;
    }
}

// Your code here

Hint

Insert all words first. Then search for prefix 'app' and print the list of matching words.

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