Trie Insert Operation in DSA Javascript - Build from Scratch

Trie Insert Operation

📖 Scenario: Imagine you are building a simple search helper that stores words so you can quickly check if a word exists later. You will create a Trie, a tree-like structure where each node represents a letter. This helps in fast word lookup.

🎯 Goal: You will build the insert operation for a Trie. This means adding words letter by letter into the Trie structure.

📋 What You'll Learn

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

Create a Trie class with a root node

Add an insert method to the Trie class that adds a word letter by letter

Print the root node's children keys after inserting words to show the Trie structure

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding Tries helps in roles involving search engines, text processing, and efficient data retrieval.

1

Create TrieNode and Trie classes

Create a class called TrieNode with a constructor that initializes children as an empty object and isEndOfWord as false. Then create a class called Trie with a constructor that initializes root as a new TrieNode.

DSA Javascript

// Create TrieNode and Trie classes with constructors
// Your code here

Hint

Think of TrieNode as a box holding letters and a flag for word end. Trie starts with an empty root node.

2

Add insert method to Trie

Inside the Trie class, add a method called insert that takes a parameter word. Initialize a variable current to this.root.

DSA Javascript

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

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

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

Hint

Start the insert method by pointing to the root node. You will move through the Trie from here.

3

Complete insert method to add letters

In the insert method, use a for loop with variable char to go through each letter of word. For each char, if current.children[char] does not exist, set it to a new TrieNode(). Then update current to current.children[char]. After the loop, set current.isEndOfWord to true.

DSA Javascript

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

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

    insert(word) {
        let current = this.root;
        // Add letters of word to Trie
        // Your code here
    }
}

Hint

Check if the letter exists in children. If not, create a new node. Move current to that node. Mark the end of the word after the loop.

4

Insert words and print Trie root children keys

Create a new Trie instance called trie. Insert the words "cat", "car", and "dog" using the insert method. Then print Object.keys(trie.root.children) to show the first letters stored in the Trie.

DSA Javascript

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

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

    insert(word) {
        let current = this.root;
        for (const char of word) {
            if (!current.children[char]) {
                current.children[char] = new TrieNode();
            }
            current = current.children[char];
        }
        current.isEndOfWord = true;
    }
}

// Create Trie instance, insert words, and print root children keys
// Your code here

Hint

Insert each word using insert. Then print the keys of trie.root.children to see the first letters stored.