Trie Insert Operation in DSA Typescript - Build from Scratch

Trie Insert Operation

📖 Scenario: Imagine you are building a simple search suggestion system. You want to store words so that you can quickly find if a word exists or suggest words starting with a prefix.

🎯 Goal: You will build a basic Trie data structure and implement the insert operation to add words to it.

📋 What You'll Learn

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

Create a Trie class with a root node

Implement an insert method in the Trie class to add words

Insert the words "cat", "car", and "dog" into the trie

Print the root node's children keys after insertion

💡 Why This Matters

🌍 Real World

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

💼 Career

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

1

Create TrieNode and Trie classes

Create a class called TrieNode with a children property as a Map<string, TrieNode> and a boolean isEndOfWord initialized to false. Then create a class called Trie with a root property initialized as a new TrieNode.

DSA Typescript

// Define TrieNode class
// Define Trie class with root node
// Your code here

Hint

Use Map to store children nodes. Initialize isEndOfWord to false.

2

Add insert method to Trie

Inside the Trie class, add a method called insert that takes a word string. Initialize a variable current to this.root. This method will add nodes for each character in word if they don't exist.

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

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

Hint

Loop over each character in word. Check if children has the character. If not, add a new TrieNode. Move current to the child node. After the loop, mark current.isEndOfWord as true.

3

Insert words into the Trie

Create a new Trie instance called trie. Use the insert method to add the words "cat", "car", and "dog" to the trie.

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 trie and insert words below
// Your code here

Hint

Create a Trie object and call insert with the exact words "cat", "car", and "dog".

4

Print root children keys

Print the keys of the root.children map of the trie instance using console.log. Use Array.from(trie.root.children.keys()) to get the keys as an array.

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

const trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");

// Print root children keys below
// Your code here

Hint

Use console.log(Array.from(trie.root.children.keys())) to print the first letters of inserted words.