Frontend School
DashboardProblemsLearnPracticeMock InterviewReportsStatsBuy Credits
DashboardProblemsLearnPracticeMock Interview
DSA for Frontend Engineers
  1. 1.Introduction to DSA for Frontend Engineers
  2. 2.JavaScript Fundamentals for DSA
  3. 3.Arrays and Strings: Core Techniques
  4. 4.Objects and Hash Maps in JavaScript
  5. 5.Linked Lists: Building Blocks
  6. 6.Stacks and Queues: LIFO & FIFO
  7. 7.Recursion and Iteration: Problem Solving Paradigms
  8. 8.Introduction to Trees: Binary Trees & BSTs
  9. 9.Tree Traversal Algorithms (BFS & DFS)
  10. 10.Sorting Algorithms I: Basics
  11. 11.Sorting Algorithms II: Divide & Conquer
  12. 12.Searching Algorithms: Linear & Binary Search
  13. 13.Graphs: Representation & Traversals
  14. 14.Dynamic Programming I: Memoization
  15. 15.Heaps and Priority Queues
  16. 16.Tries (Prefix Trees) for Autocomplete & Search
  17. 17.Advanced Graph Algorithms: Shortest Paths & MST
  18. 18.Dynamic Programming II: Tabulation & Frontend Patterns
  19. 19.Frontend System Design with DSA Lens
  20. 20.Interview Strategies & Advanced Problem Solving
DSA for Frontend Engineers
16

DSA · Lesson 16 of 20 · 3 min

Tries (Prefix Trees) for Autocomplete & Search

This is the default answer for "design an autocomplete system" and a common way to optimize string-matching problems.

Why not just Array.prototype.filter?

For a small list of options, filtering an array on every keystroke works. For a list of 10,000 product names, it's a performance disaster.

products.filter(p => p.startsWith(userInput)) has to iterate through all 10,000 strings. If the average string length is 20, that's 200,000 character comparisons per keystroke. This will block the main thread and create a janky user experience.

A Trie changes the complexity from O(N * L) (where N is the list size and L is average string length) to O(P) (where P is the length of the typed prefix). The lookup time is independent of the number of words in the dictionary. This is the trade-off: you use more memory to get significantly faster lookups.

How a Trie works

A Trie stores strings by breaking them into characters. Each node represents a character, and a path from the root to a node represents a prefix. The root is an empty string.

Each node contains a map of its children ('a' -> TrieNode, 'b' -> TrieNode, etc.) and a boolean flag, isEndOfWord.

The trap: Forgetting the isEndOfWord flag. A common mistake is assuming that reaching a node means you've found a word. The path "a-p-p-l" exists for "apple", but "appl" is not a valid word in our dictionary. The flag distinguishes prefixes from complete words.

This structure for "app", "apple", and "apply" looks like this:

The time complexity for insertion, search, and prefix checking is always O(L), where L is the length of the word or prefix. Space complexity is proportional to the total number of characters in all stored words.

A complete implementation

Here is a self-contained Trie implementation in TypeScript. It includes the node definition and the core methods for insertion, search, and generating autocomplete suggestions.

class TrieNode {
    children: Map<string, TrieNode>;
    isEndOfWord: boolean;

    constructor() {
        // Map is better than a fixed-size array for sparse character sets (e.g., Unicode).
        this.children = new Map<string, TrieNode>();
        this.isEndOfWord = false;
    }
}

class Trie {
    private root: TrieNode;

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

    // O(L) time, where L is word length
    insert(word: string): void {
        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)!;
        }
        node.isEndOfWord = true;
    }

    // O(L) time, where L is word length
    search(word: string): boolean {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                return false;
            }
            node = node.children.get(char)!;
        }
        // Must be a complete word, not just a prefix.
        return node.isEndOfWord;
    }

    // O(P) time, where P is prefix length
    startsWith(prefix: string): boolean {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children.has(char)) {
                return false;
            }
            node = node.children.get(char)!;
        }
        return true;
    }

    // O(P + K) time, P = prefix length, K = total chars in all matching words
    getSuggestions(prefix: string): string[] {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children.has(char)) {
                return []; // No words with this prefix.
            }
            node = node.children.get(char)!;
        }

        const suggestions: string[] = [];
        // Use a recursive helper to perform DFS from the prefix node.
        const collectWords = (currentNode: TrieNode, currentWord: string) => {
            if (currentNode.isEndOfWord) {
                suggestions.push(currentWord);
            }
            for (const [char, childNode] of currentNode.children.entries()) {
                collectWords(childNode, currentWord + char);
            }
        };

        collectWords(node, prefix);
        return suggestions;
    }
}

How to answer "design a typeahead"

This is a classic system design question, even for frontend roles. The Trie is the core of your answer.

Start by clarifying constraints. How large is the dataset? Where does it come from? Is it static or dynamic? How many suggestions should we show?

For a small, bounded dataset (e.g., country names, command palettes, user tags in a small team), a client-side Trie is the best solution. You initialize the Trie once with the full list. Each keystroke calls getSuggestions(), which is extremely fast.

For a massive dataset (e.g., Google search, all products on Amazon), a client-side Trie would consume too much memory. The solution is a backend service. The client sends debounced requests to an API (/api/search?q=...), and the backend uses a Trie (or a more advanced text-search engine like Elasticsearch) to find and return a short list of suggestions.

Be ready for follow-up questions:

  • Ranking: "How do you show the most popular suggestions first?" Store a frequency or weight property in each TrieNode. When collecting words, sort them by this weight before returning.
  • Deletion: "How do you remove a word?" Find the word's final node and set isEndOfWord to false. Then, you can optionally clean up by walking back up the tree and removing any nodes that are no longer part of any other word.
  • Wildcard Search: "How would you match c.t to cat?" Your search function needs to branch. When it encounters a wildcard, it must recursively try the search path for every child of the current node.

Try it

Implement a Trie and populate it with a list of 100 common English words. Add a method findLongestWord() that traverses the Trie to find and return the longest word stored. This forces you to think about traversal beyond just prefix search. You can solve these related problems for more practice: Implement Trie (Prefix Tree) and Word Search II.

Next: We'll move from trees to a more general structure in Advanced Graph Algorithms: Shortest Paths & MST.

Lock it in — apply this lesson under interview conditions.

Try a free mock interviewPractice this pattern
Previous

Heaps and Priority Queues

Next

Advanced Graph Algorithms: Shortest Paths & MST