Autocomplete System with Trie in DSA Typescript - 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 form where each node represents a letter.

🎯 Goal: Create a Trie to store a list of words. Then, given a prefix, find all words in the Trie that start with that prefix.This project will help you understand how Tries work and how they can be used for autocomplete features.

📋 What You'll Learn

Create a TrieNode class with a children map and an endOfWord boolean

Create a Trie class with insert and searchPrefix methods

Insert given words into the Trie

Find all words starting with a given prefix using the Trie

Print the list of autocomplete suggestions

💡 Why This Matters

🌍 Real World

Autocomplete systems are used in search engines, messaging apps, and code editors to help users find words quickly by typing just a few letters.

💼 Career

Understanding Tries and autocomplete logic is useful for software engineers working on search features, user interfaces, and performance optimization.

1

Create TrieNode class

Create a class called TrieNode with a children property as a Map<string, TrieNode> and a endOfWord property set to false.

DSA Typescript

# Your code here

Hint

Think of TrieNode as a box holding links to next letters and a flag if a word ends here.

2

Create Trie class with insert method

Create a class called Trie with a root property initialized as a new TrieNode. Add an insert method that takes a word: string and inserts it into the Trie by creating nodes for each letter and marking the last node's endOfWord as true.

DSA Typescript

class TrieNode {
    children: Map;
    endOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.endOfWord = false;
    }
}

// Create Trie class with root and insert method
// Your code here

Hint

Insert each letter by checking if it exists in children, create if missing, then move to that node.

3

Add searchPrefix method to find node for prefix

Add a method searchPrefix to the Trie class that takes a prefix: string and returns the TrieNode where the prefix ends, or null if the prefix is not found.

DSA Typescript

class TrieNode {
    children: Map;
    endOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.endOfWord = false;
    }
}

class Trie {
    root: TrieNode;

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

    insert(word: string): void {
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new TrieNode());
            }
            current = current.children.get(char)!;
        }
        current.endOfWord = true;
    }

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

Hint

Traverse the Trie nodes for each letter in prefix. If any letter is missing, return null.

4

Find and print autocomplete suggestions for a prefix

Write a function autocomplete that takes a prefix: string and a trie: Trie. Use searchPrefix to find the node for the prefix. Then, recursively collect all words starting from that node by exploring children. Finally, print the list of words starting with the prefix using console.log.

DSA Typescript

class TrieNode {
    children: Map;
    endOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.endOfWord = false;
    }
}

class Trie {
    root: TrieNode;

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

    insert(word: string): void {
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new TrieNode());
            }
            current = current.children.get(char)!;
        }
        current.endOfWord = true;
    }

    searchPrefix(prefix: string): TrieNode | null {
        let current = this.root;
        for (const char of prefix) {
            if (!current.children.has(char)) {
                return null;
            }
            current = current.children.get(char)!;
        }
        return current;
    }
}

const trie = new Trie();
const words = ["apple", "app", "apricot", "banana", "bat", "bath", "batman"];
for (const word of words) {
    trie.insert(word);
}

// Write autocomplete function and print suggestions for prefix "ba"
// Your code here

Hint

Use a helper function to explore all children nodes recursively and collect words.

Print the final list with console.log.