Prefix Search Using Trie in DSA Typescript - Build from Scratch

Prefix Search Using Trie

📖 Scenario: You are building a simple search feature for a phone contacts app. When a user types some letters, the app should quickly find all contact names that start with those letters.To do this efficiently, you will use a Trie data structure, which stores words by their letters in a tree form.

🎯 Goal: Build a Trie to store contact names and write a function to find all contacts starting with a given prefix.

📋 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 contact names into the Trie

Write a function to find all contacts starting with a given prefix

Print the list of contacts found for the prefix

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words starting with certain letters.

💼 Career

Understanding Tries helps in roles involving search optimization, text processing, and building efficient data retrieval systems.

1

Create TrieNode and Trie classes

Create a class called TrieNode with a children property as a Map from string to TrieNode and a endOfWord boolean property set to false. Then create a class called Trie with a root property initialized as a new TrieNode. Add an insert method to Trie that takes a word string and inserts it into the trie letter by letter.

DSA Typescript

// Your code here to create TrieNode and Trie classes with insert method

Hint

Think of TrieNode as a box holding letters and a flag if a word ends there. The Trie has a root box and an insert method to add words letter by letter.

2

Insert contact names into the Trie

Create a string array called contacts with these exact names: 'alice', 'alex', 'bob', 'bobby', 'carol'. Then create a Trie instance called trie and insert each contact from contacts into trie using the insert method.

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;
    }
}

// Create contacts array and insert each into trie
// Your code here

Hint

Make an array with the exact contact names. Then create a Trie and add each contact using the insert method.

3

Add searchPrefix method to find all contacts starting with a prefix

Add a method called searchPrefix to the Trie class. It takes a prefix string and returns a string array of all words in the trie that start with that prefix. Use a helper function inside searchPrefix to recursively collect all words starting from the node matching the prefix.

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
}

const contacts: string[] = ['alice', 'alex', 'bob', 'bobby', 'carol'];
const trie = new Trie();
for (const contact of contacts) {
    trie.insert(contact);
}

Hint

First find the node matching the prefix. Then use a helper function to explore all children nodes and collect words that end there.

4

Print contacts starting with prefix 'bo'

Use the searchPrefix method of trie to find all contacts starting with the prefix 'bo'. Store the result in a variable called results and print it using console.log(results).

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): string[] {
        let current = this.root;
        for (const char of prefix) {
            if (!current.children.has(char)) {
                return [];
            }
            current = current.children.get(char)!;
        }

        const results: string[] = [];

        const dfs = (node: TrieNode, path: string) => {
            if (node.endOfWord) {
                results.push(path);
            }
            for (const [char, childNode] of node.children) {
                dfs(childNode, path + char);
            }
        };

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

const contacts: string[] = ['alice', 'alex', 'bob', 'bobby', 'carol'];
const trie = new Trie();
for (const contact of contacts) {
    trie.insert(contact);
}

// Your code here to search prefix 'bo' and print results

Hint

Call searchPrefix with 'bo' and print the returned array.