Welcome back, aspiring data structures and algorithms expert! In this chapter, we’re going to put our knowledge of Tries into action by building a practical and highly useful application: an autocomplete system. Autocomplete is everywhere – from search bars and messaging apps to code editors and command-line interfaces. It significantly enhances user experience by providing instant, relevant suggestions as you type.

You’ve already learned about Tries (also known as prefix trees) in a previous chapter. Now, we’ll see exactly why they are the perfect data structure for this kind of problem. Their ability to efficiently store and retrieve strings based on common prefixes makes them an ideal choice for quickly finding all words that start with a given input. Get ready to build something cool and reinforce your understanding of this powerful data structure!

By the end of this chapter, you will have:

  • A fully functional autocomplete system implemented in TypeScript.
  • A deeper understanding of how Tries enable efficient prefix searching.
  • Experience in designing a practical application using DSA principles.
  • Confidence in applying data structures to solve real-world problems.

Let’s dive in and build our autocomplete engine!

Core Concepts: Tries for Autocomplete

Before we start coding, let’s quickly recap the fundamental idea of a Trie and why it’s so well-suited for autocomplete.

Imagine you’re typing “appl” into a search bar. An autocomplete system should suggest “apple”, “application”, “apply”, etc.

Why Tries?

A Trie stores words character by character, where each node represents a character, and the path from the root to a node represents a prefix.

  • Efficient Prefix Matching: To find all words starting with “appl”, we just traverse the Trie along the path ‘a’ -> ‘p’ -> ‘p’ -> ’l’. Once we reach the node corresponding to ’l’, all words in the subtree rooted at ’l’ will have “appl” as their prefix. This traversal is incredibly fast, proportional to the length of the prefix, not the number of words in the dictionary.
  • Space Optimization: If many words share common prefixes (e.g., “apple”, “apply”, “application”), the Trie reuses the nodes for those common prefixes, which can save memory compared to storing each word independently in a hash set, especially for large dictionaries with many related words.
  • Ordered Suggestions (with slight modification): While not inherent, Tries can be adapted to return suggestions in alphabetical order or by frequency if additional information is stored in the nodes. For our basic implementation, we’ll just return all matching words.

TrieNode Structure for Autocomplete

Each node in our Trie will need two main pieces of information:

  1. children: A Map or an object that links characters to their respective child TrieNodes. For example, if a node represents ‘a’, its children might contain an entry mapping ‘p’ to the TrieNode for ‘p’.
  2. isEndOfWord: A boolean flag indicating whether the path from the root to this node constitutes a complete, valid word. This is crucial for distinguishing between prefixes that are also words (like “a” or “an”) and prefixes that are just parts of longer words.

Trie Class Structure

Our Trie class will encapsulate the entire data structure and provide methods for common operations:

  • constructor(): Initializes the root node of the Trie.
  • insert(word: string): Adds a new word to the Trie.
  • searchPrefix(prefix: string): A helper method that finds and returns the TrieNode corresponding to the end of a given prefix. This will be invaluable for our autocomplete logic.
  • getWordsWithPrefix(prefix: string): The core autocomplete method. It will find all words in the Trie that start with the provided prefix.

Ready to build this step-by-step? Let’s get our hands dirty!

Step-by-Step Implementation

1. Project Setup

First, let’s set up our TypeScript project.

  1. Create a new directory for our project and navigate into it:

    mkdir trie-autocomplete
cd trie-autocomplete

  2. Initialize a Node.js project:

    npm init -y

    This creates a package.json file.

  3. Install TypeScript:

    npm install typescript --save-dev

    We install TypeScript as a development dependency.

  4. Initialize TypeScript configuration:

    npx tsc --init

    This creates a tsconfig.json file, which configures the TypeScript compiler.

  5. Adjust tsconfig.json: Open tsconfig.json and make sure the following settings are present and uncommented (or similar, based on your preference; these are good defaults for Node.js projects):

    {
  "compilerOptions": {
    "target": "ES2022",                       /* Specify ECMAScript target version: "ES3" (default), "ES5", "ES2015", "ES2016", "ES2017", "ES2018", "ES2019", "ES2020", "ES2021", "ES2022", "ESNext". */
    "module": "CommonJS",                     /* Specify module code generation: "None", "CommonJS", "AMD", "System", "UMD", "ES6", "ES2015", "ES2020", "ES2022", "ESNext", "Node16", "NodeNext". */
    "outDir": "./dist",                       /* Specify an output folder for all emitted files. */
    "rootDir": "./src",                       /* Specify the root folder within your source files. */
    "esModuleInterop": true,                  /* Emit additional JavaScript to ease support for importing CommonJS modules. This enables 'allowSyntheticDefaultImports' for type compatibility. */
    "forceConsistentCasingInFileNames": true, /* Ensure that casing is correct in imports. */
    "strict": true,                           /* Enable all strict type-checking options. */
    "skipLibCheck": true                      /* Skip type checking all .d.ts files. */
  }
}

    We’re setting target to ES2022 for modern JavaScript features, module to CommonJS for Node.js, outDir to dist for compiled JavaScript, and rootDir to src for our source TypeScript files. strict mode is always a good idea!

  6. Create source files: Create a src folder and inside it, create trie.ts and index.ts:

    mkdir src
touch src/trie.ts src/index.ts

2. Implementing the TrieNode Class (src/trie.ts)

Let’s start by defining our TrieNode.

Open src/trie.ts and add the following:

// src/trie.ts

/**
 * Represents a single node in the Trie data structure.
 * Each node stores a map of its children and a flag indicating if it marks the end of a word.
 */
export class TrieNode {
    // A map where keys are characters and values are child TrieNodes.
    // This allows us to efficiently find the next character in a word.
    public children: Map<string, TrieNode>;

    // A boolean flag that is true if this node represents the end of a valid word.
    // For example, in a Trie containing "apple" and "apply", the node for 'e' in "apple"
    // would have isEndOfWord = true, but the node for 'l' in "apple" would not.
    public isEndOfWord: boolean;

    constructor() {
        this.children = new Map<string, TrieNode>();
        this.isEndOfWord = false;
    }
}

Explanation:

  • We define TrieNode as a class.
  • children: This Map is the heart of the Trie. It stores references to subsequent TrieNodes, keyed by the character they represent. Using Map<string, TrieNode> is efficient for character lookups.
  • isEndOfWord: This boolean is crucial. It tells us if the path leading to this node forms a complete word. Without it, we couldn’t distinguish between “app” (a word) and “appl” (a prefix of “apple”).

3. Implementing the Trie Class (src/trie.ts)

Now, let’s build the Trie class itself, adding its methods one by one.

Continue in src/trie.ts and add the Trie class below the TrieNode class.

Constructor 

// src/trie.ts (add below TrieNode)

/**
 * Implements the Trie (Prefix Tree) data structure for efficient
 * storage and retrieval of words based on their prefixes.
 */
export class Trie {
    // The root node of the Trie. It typically doesn't represent any character,
    // but serves as the starting point for all word insertions and searches.
    private root: TrieNode;

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

    // ... (rest of the Trie methods will go here)
}

Explanation:

  • Our Trie class holds a reference to its root TrieNode. This root node is special; it doesn’t represent any character itself, but acts as the entry point to our entire dictionary.

insert Method

This method adds a word to our Trie.

Add this method inside the Trie class:

// src/trie.ts (inside Trie class)

    /**
     * Inserts a word into the Trie.
     * It traverses the Trie character by character, creating new nodes if a path doesn't exist.
     * Finally, it marks the end of the word.
     * @param word The word to insert.
     */
    public insert(word: string): void {
        let currentNode = this.root;
        // Iterate through each character of the word
        for (const char of word) {
            // If the current node doesn't have a child for this character, create one
            if (!currentNode.children.has(char)) {
                currentNode.children.set(char, new TrieNode());
            }
            // Move to the next node (the child corresponding to the current character)
            currentNode = currentNode.children.get(char)!; // The '!' asserts that it won't be undefined
        }
        // After iterating through all characters, mark the last node as the end of a word
        currentNode.isEndOfWord = true;
    }

Explanation:

  • We start at the root.
  • For each character in the word:
    • We check if the currentNode already has a child for this character. If not, we create a new TrieNode and add it to currentNode.children.
    • We then move currentNode to this child node.
  • Once all characters are processed, the currentNode is at the end of the word’s path. We set currentNode.isEndOfWord = true.

searchPrefix Helper Method

This private helper method will be useful for finding the node that represents the end of a given prefix.

Add this method inside the Trie class:

// src/trie.ts (inside Trie class)

    /**
     * Helper method to find the TrieNode corresponding to the end of a given prefix.
     * @param prefix The prefix to search for.
     * @returns The TrieNode at the end of the prefix path, or null if the prefix is not found.
     */
    private searchPrefix(prefix: string): TrieNode | null {
        let currentNode = this.root;
        // Traverse the Trie using the characters of the prefix
        for (const char of prefix) {
            // If a child node for the current character doesn't exist, the prefix is not in the Trie
            if (!currentNode.children.has(char)) {
                return null;
            }
            // Move to the next node
            currentNode = currentNode.children.get(char)!;
        }
        // If we successfully traversed the entire prefix, return the node we ended up on
        return currentNode;
    }

Explanation:

  • Similar to insert, we traverse the Trie character by character, following the path of the prefix.
  • If at any point we encounter a character for which there is no child node, it means the prefix does not exist in our Trie, so we return null.
  • If we successfully traverse the entire prefix, we return the TrieNode where the traversal ended. This node represents the end of the prefix.

getWordsWithPrefix Method (Core Autocomplete Logic)

This is where the magic happens for autocomplete! We’ll use our searchPrefix helper and then perform a Depth-First Search (DFS) from the prefix node.

Add this method and its DFS helper inside the Trie class:

// src/trie.ts (inside Trie class)

    /**
     * Finds all words in the Trie that start with the given prefix.
     * This is the core logic for our autocomplete feature.
     * @param prefix The prefix to search for.
     * @returns An array of words that start with the given prefix.
     */
    public getWordsWithPrefix(prefix: string): string[] {
        const results: string[] = [];
        // First, find the node that corresponds to the end of the prefix.
        const prefixNode = this.searchPrefix(prefix);

        // If the prefix itself is not found in the Trie, there are no words with this prefix.
        if (!prefixNode) {
            return results;
        }

        // Now, perform a Depth-First Search (DFS) starting from the prefixNode.
        // This helper function will recursively explore all paths from prefixNode
        // to find all complete words.
        const dfs = (node: TrieNode, currentWord: string) => {
            // If the current node marks the end of a word, add the word to our results.
            if (node.isEndOfWord) {
                results.push(currentWord);
            }

            // Recursively visit all children of the current node.
            for (const [char, childNode] of node.children) {
                dfs(childNode, currentWord + char);
            }
        };

        // Start the DFS from the prefixNode, with the prefix itself as the starting word fragment.
        dfs(prefixNode, prefix);

        return results;
    }

Explanation:

  • We initialize an empty results array to store our suggestions.
  • We use this.searchPrefix(prefix) to get the TrieNode that represents the end of the input prefix.
  • If prefixNode is null, it means the prefix doesn’t exist, so we return an empty array.
  • If prefixNode exists, we define a recursive helper function dfs (Depth-First Search).
    • dfs takes a node and the currentWord built so far.
    • If node.isEndOfWord is true, it means we’ve found a complete word, so we add currentWord to results.
    • Then, dfs iterates through all children of the node, recursively calling itself for each child, appending the child’s character to currentWord.
  • Finally, we kick off the dfs from prefixNode, initializing currentWord with the prefix itself.

4. Putting It All Together and Testing (src/index.ts)

Now, let’s use our Trie class to create an autocomplete demonstration.

Open src/index.ts and add the following code:

// src/index.ts

import { Trie } from './trie'; // Import our Trie class

// 1. Create a new Trie instance
const autocompleteTrie = new Trie();

// 2. Define a dictionary of words to populate our Trie
const dictionary: string[] = [
    "apple", "application", "apply", "apricot", "api",
    "banana", "bandana", "bank", "batch", "basic",
    "cat", "catalog", "catch", "code", "coder",
    "data", "database", "datastructure", "dog",
    "elephant", "engine", "engineer",
    "function", "fundamental", "future"
];

// 3. Insert all words from the dictionary into the Trie
console.log("Populating Trie with dictionary words...");
for (const word of dictionary) {
    autocompleteTrie.insert(word);
}
console.log(`Trie populated with ${dictionary.length} words.\n`);

// 4. Test the autocomplete functionality with various prefixes
const testPrefixes: string[] = ["ap", "app", "ban", "c", "dat", "eng", "z", "co"];

for (const prefix of testPrefixes) {
    console.log(`Searching for suggestions for prefix: "${prefix}"`);
    const suggestions = autocompleteTrie.getWordsWithPrefix(prefix);
    if (suggestions.length > 0) {
        console.log(`  Suggestions: ${suggestions.join(', ')}`);
    } else {
        console.log(`  No suggestions found for "${prefix}".`);
    }
    console.log("---------------------------------------");
}

To run your autocomplete system:

  1. Compile the TypeScript code:

    npx tsc

    This command will compile src/trie.ts and src/index.ts into JavaScript files in the dist directory.

  2. Run the compiled JavaScript code:

    node dist/index.js

You should see output similar to this:

Populating Trie with dictionary words...
Trie populated with 22 words.

Searching for suggestions for prefix: "ap"
  Suggestions: apple, application, apply, apricot, api
---------------------------------------
Searching for suggestions for prefix: "app"
  Suggestions: apple, application, apply
---------------------------------------
Searching for suggestions for prefix: "ban"
  Suggestions: banana, bandana, bank
---------------------------------------
Searching for suggestions for prefix: "c"
  Suggestions: cat, catalog, catch, code, coder
---------------------------------------
Searching for suggestions for prefix: "dat"
  Suggestions: data, database, datastructure
---------------------------------------
Searching for suggestions for prefix: "eng"
  Suggestions: engine, engineer
---------------------------------------
Searching for suggestions for prefix: "z"
  No suggestions found for "z".
---------------------------------------
Searching for suggestions for prefix: "co"
  Suggestions: code, coder
---------------------------------------

Fantastic! You’ve just built a functional autocomplete system using a Trie. Notice how quickly it returns suggestions even for short prefixes. This efficiency is precisely why Tries are used in real-world systems for tasks like this.

Mini-Challenge: Limit Suggestions

Our current getWordsWithPrefix returns all matching words. In a real-world autocomplete UI, you usually only want to show a limited number of suggestions (e.g., the top 5 or 10) to avoid overwhelming the user.

Challenge: Modify the getWordsWithPrefix method to accept an optional limit parameter. If limit is provided, the method should return at most that many suggestions.

Hint: You can pass the limit down into your dfs helper function and stop the recursion or stop adding to results once the limit is reached. Alternatively, you could collect all results and then slice the array at the end. Which approach might be more efficient for a very large dictionary and a small limit? (Think about it!)

What to observe/learn: How to control the output of a recursive traversal and optimize for common UI constraints.

Click for HintTo make it efficient, modify the `dfs` function to include a check against the `limit`. If `results.length` reaches the `limit`, the `dfs` should stop adding new words and return early. This avoids unnecessary traversal of the Trie.
Click for Solution (after you've tried it!)

Here’s one way to implement the limit:

// src/trie.ts (modified getWordsWithPrefix method)

    public getWordsWithPrefix(prefix: string, limit?: number): string[] { // Added optional limit parameter
        const results: string[] = [];
        const prefixNode = this.searchPrefix(prefix);

        if (!prefixNode) {
            return results;
        }

        // Modified DFS to include limit checking
        const dfs = (node: TrieNode, currentWord: string) => {
            // If we've reached the limit, stop adding more words
            if (limit !== undefined && results.length >= limit) {
                return;
            }

            if (node.isEndOfWord) {
                results.push(currentWord);
            }

            for (const [char, childNode] of node.children) {
                // If limit is reached, no need to explore further children
                if (limit !== undefined && results.length >= limit) {
                    return;
                }
                dfs(childNode, currentWord + char);
            }
        };

        dfs(prefixNode, prefix);

        // If for some reason DFS didn't perfectly stop, ensure we slice to the limit
        return limit !== undefined ? results.slice(0, limit) : results;
    }

And in src/index.ts you can test it:

// src/index.ts (modified test section)

// ... (previous code)

// 4. Test the autocomplete functionality with various prefixes and a limit
const testPrefixes: string[] = ["ap", "app", "ban", "c", "dat", "eng", "z", "co"];
const suggestionLimit = 3; // Let's limit to 3 suggestions

for (const prefix of testPrefixes) {
    console.log(`Searching for suggestions for prefix: "${prefix}" (limited to ${suggestionLimit})`);
    const suggestions = autocompleteTrie.getWordsWithPrefix(prefix, suggestionLimit); // Pass the limit
    if (suggestions.length > 0) {
        console.log(`  Suggestions: ${suggestions.join(', ')}`);
    } else {
        console.log(`  No suggestions found for "${prefix}".`);
    }
    console.log("---------------------------------------");
}

Common Pitfalls & Troubleshooting

  1. Forgetting isEndOfWord: If you insert words but never set isEndOfWord = true on the final node, your getWordsWithPrefix will never find any complete words. You’ll only get suggestions if the words are also prefixes of other words, which isn’t correct.

    • Fix: Double-check your insert method to ensure currentNode.isEndOfWord = true; is called at the end of word insertion.

  2. Incorrect searchPrefix Logic: If searchPrefix doesn’t correctly find the target node or returns null when it shouldn’t, getWordsWithPrefix will either fail to find words or start its DFS from the wrong place.

    • Fix: Step through searchPrefix mentally with a simple prefix like “app” and a dictionary containing “apple” and “apply”. Ensure currentNode correctly moves through the path and returns the expected node (or null).

  3. Recursion Depth: For extremely long words or deeply nested Tries, JavaScript’s default recursion limit could theoretically be hit. However, for typical dictionary words, this is rarely an issue.

    • Fix: If you encounter a “Maximum call stack size exceeded” error, you might need to refactor the dfs to an iterative approach using an explicit stack, but this is an advanced optimization typically not needed for standard autocomplete.

  4. TypeScript Type Errors: Using Map and dealing with potentially undefined results can lead to TypeScript errors if not handled. The ! (non-null assertion operator) is used to tell TypeScript that currentNode.children.get(char) will definitely return a value in the insert and searchPrefix loops because we either just set it or checked has(char).

    • Fix: Pay attention to TypeScript’s warnings. Use if (!value) checks or non-null assertions (!) judiciously when you are certain a value won’t be null or undefined.

Summary

Congratulations! You’ve successfully built a practical autocomplete system using the Trie data structure. This project demonstrated several key takeaways:

  • Tries are powerful for prefix-based searches: They offer excellent performance for operations like finding all words starting with a particular string.
  • Real-world application: Autocomplete is a prime example of how data structures directly translate into enhanced user experience in applications.
  • Incremental development: We built our system step-by-step, starting with the basic TrieNode, then the Trie class methods, and finally integrating them into an executable program.
  • Problem-solving mindset: We designed a dfs helper to efficiently traverse the Trie’s subtrees to collect all relevant suggestions.

You’ve now seen a Trie in action and understand its practical value. This is a significant step in applying your DSA knowledge to build efficient software!

What’s Next?

In the next chapter, we’ll continue exploring more advanced data structures or move into another algorithmic paradigm, further expanding your toolkit for tackling complex programming challenges. Keep practicing and experimenting!

References

This page is AI-assisted and reviewed. It references official documentation and recognized resources where relevant.