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.