Trie Search Operation in DSA Typescript - Build from Scratch

Trie Search Operation

📖 Scenario: You are building a simple word search tool for a small dictionary. The tool uses a Trie data structure to store words and quickly check if a word exists.

🎯 Goal: Build a Trie with given words and implement a search operation to check if a word is present in the Trie.

📋 What You'll Learn

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

Create a Trie class with insert and search methods

Insert given words into the Trie

Search for a given word in the Trie and return true if found, false otherwise

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and IP routing to quickly find words or prefixes.

💼 Career

Understanding Trie search operations is important for roles involving text processing, search engines, and efficient data retrieval.

1

Create TrieNode and Trie classes with insert method

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

DSA Typescript

// Define TrieNode and Trie classes with insert method
// Your code here

Hint

Use a Map to store children nodes and a boolean to mark the end of a word. Insert each character by creating new nodes if needed.

2

Insert given words into the Trie

Create a variable called words as an array of strings with these exact values: "cat", "car", "dog", "door". Then create a variable called trie as a new instance of the Trie class. Use a for loop with variable word to iterate over words and insert each word into trie using the insert method.

DSA Typescript

class TrieNode {
    children: Map;
    isEndOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.isEndOfWord = 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.isEndOfWord = true;
    }
}

// Create words array and insert each word into trie
// Your code here

Hint

Create the array with exact words and loop through it to insert each word into the trie.

3

Add search method to Trie class

Add a method called search to the Trie class that takes a word string and returns a boolean. The method should start from this.root and for each character in word, check if the character exists in the current node's children. If not, return false. If all characters are found, return the isEndOfWord value of the last node.

DSA Typescript

class TrieNode {
    children: Map;
    isEndOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.isEndOfWord = 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.isEndOfWord = true;
    }

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

const words: string[] = ["cat", "car", "dog", "door"];
const trie = new Trie();
for (const word of words) {
    trie.insert(word);
}

Hint

Traverse the trie nodes for each character. If a character is missing, return false. After the loop, return if the last node marks the end of a word.

4

Search for words and print results

Use console.log to print the result of trie.search("car") and trie.search("cow"). The output should be true for "car" and false for "cow".

DSA Typescript

class TrieNode {
    children: Map;
    isEndOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.isEndOfWord = 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.isEndOfWord = true;
    }

    search(word: string): boolean {
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) {
                return false;
            }
            current = current.children.get(char)!;
        }
        return current.isEndOfWord;
    }
}

const words: string[] = ["cat", "car", "dog", "door"];
const trie = new Trie();
for (const word of words) {
    trie.insert(word);
}

// Print search results for "car" and "cow"
// Your code here

Hint

Use console.log to print the boolean results of searching "car" and "cow" in the trie.