Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Javascript - See It Work

Why Trie Exists and What Hash Map Cannot Do for Strings

📖 Scenario: Imagine you are building a search feature for a phone contact list app. You want to quickly find all contacts starting with certain letters as the user types. A simple hash map can find exact matches fast, but it struggles with partial matches or prefix searches.We will explore why a Trie (prefix tree) is better for this task and what problems a hash map cannot solve easily for strings.

🎯 Goal: Build a simple Trie data structure to store a list of contact names. Then, search for all contacts starting with a given prefix. This shows why Trie is useful beyond what a hash map can do.

📋 What You'll Learn

Create a Trie node structure with children and end-of-word marker

Insert multiple contact names into the Trie

Search for all contacts starting with a given prefix

Print the list of matched contacts

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers where prefix matching is common.

💼 Career

Understanding Tries helps in roles involving search optimization, text processing, and building efficient string-based data structures.

1

Create the Trie Node and Insert Function

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. Add a method called insert in Trie that takes a string word and inserts it into the Trie letter by letter, marking the end of the word.

DSA Javascript

// Create TrieNode class with children and isEndOfWord
// Create Trie class with root as TrieNode
// Add insert(word) method to Trie
// Your code here

Hint

Think of each letter as a branch in a tree. Insert letters one by one, creating new branches if needed.

2

Insert Multiple Contact Names into the Trie

Create a variable called contacts and assign it the array ["alice", "alex", "bob", "bobby", "carol"]. Then create a variable called trie as a new instance of Trie. Use a for loop with variable name to insert each contact from contacts into trie using the insert method.

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 contacts array and insert each name into trie
// Your code here

Hint

Use a loop to add each contact name to the Trie using the insert method.

3

Add Search Method to Find Contacts by Prefix

Add a method called searchPrefix to the Trie class that takes a string prefix. It should traverse the Trie nodes following the prefix letters. If the prefix is not found, return an empty array. Otherwise, collect all words in the Trie that start with the prefix by traversing from the prefix node. Use a helper function inside searchPrefix called dfs that takes a node and path string, and adds complete words to a results array. Return the results array at the end.

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

    // Add searchPrefix(prefix) method here
    // Your code here
}

const contacts = ["alice", "alex", "bob", "bobby", "carol"];
const trie = new Trie();
for (const name of contacts) {
    trie.insert(name);
}

Hint

Traverse the Trie for the prefix, then use a depth-first search to find all words starting from that node.

4

Print Contacts Matching a Given Prefix

Create a variable called prefix and set it to "bo". Then use console.log to print the result of calling trie.searchPrefix(prefix).

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

    searchPrefix(prefix) {
        let current = this.root;
        for (const char of prefix) {
            if (!current.children[char]) {
                return [];
            }
            current = current.children[char];
        }

        const results = [];
        const dfs = (node, path) => {
            if (node.isEndOfWord) {
                results.push(path);
            }
            for (const child in node.children) {
                dfs(node.children[child], path + child);
            }
        };

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

const contacts = ["alice", "alex", "bob", "bobby", "carol"];
const trie = new Trie();
for (const name of contacts) {
    trie.insert(name);
}

// Create prefix variable and print search results
// Your code here

Hint

Set prefix to "bo" and print the array returned by searchPrefix to see matching contacts.