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.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing many strings?

easy

A. Because Trie automatically sorts strings alphabetically.

B. Because Trie uses less memory than a Hash Map for any data.

C. Because Hash Map cannot store strings as keys.

D. Because Trie can efficiently find all words with a given prefix, which Hash Map cannot do easily.

Solution

1. Step 1: Understand Trie prefix search

   Trie stores strings character by character, allowing quick prefix lookups.

2. Step 2: Compare with Hash Map capabilities

   Hash Map stores full keys but cannot efficiently find all keys sharing a prefix without checking all keys.

3. Final Answer:

   Because Trie can efficiently find all words with a given prefix, which Hash Map cannot do easily. -> Option D

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie = prefix search; Hash Map = exact key only [OK]

Common Mistakes:

• Thinking Hash Map can do prefix search efficiently
• Believing Trie always uses less memory
• Assuming Hash Map cannot store string keys

2. Which of the following is the correct way to initialize an empty Trie node in JavaScript?

easy

A. const node = null;

B. const node = new Map();

C. const node = { children: {}, isEndOfWord: false };

D. const node = [];

Solution

1. Step 1: Identify Trie node structure

   A Trie node typically has a children object for next letters and a boolean to mark word end.

2. Step 2: Match with options

   const node = { children: {}, isEndOfWord: false }; correctly creates an object with children as empty object and isEndOfWord as false.

3. Final Answer:

   const node = { children: {}, isEndOfWord: false }; -> Option C

4. Quick Check:

   Trie node = object with children and end flag [OK]

Hint: Trie node = object with children map and end flag [OK]

Common Mistakes:

• Using array instead of object for children
• Using null instead of an object
• Using Map without isEndOfWord flag

3. What will be the output of the following code snippet?

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

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }
  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEndOfWord;
  }
}

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
console.log(trie.search('cat'));
console.log(trie.search('cap'));

medium

A. true true

B. true false

C. false true

D. false false

Solution

1. Step 1: Insert 'cat' and 'car' into Trie

   Both words are added character by character, marking end of word at last character.

2. Step 2: Search 'cat' and 'cap'

   'cat' exists and ends at isEndOfWord true, so returns true. 'cap' path breaks at 'p' missing, returns false.

3. Final Answer:

   true false -> Option B

4. Quick Check:

   Search 'cat' = true, 'cap' = false [OK]

Hint: Search returns true only if full word inserted before [OK]

Common Mistakes:

• Assuming partial prefix returns true
• Confusing isEndOfWord flag
• Missing character check in search

4. The following code tries to insert words into a Trie but has a bug. What is the bug?

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

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    // Missing line here
  }
}

medium

A. The code does not mark the end of the word after insertion.

B. The code uses an object instead of a Map for children.

C. The constructor does not initialize the root node.

D. The loop does not iterate over each character of the word.

Solution

1. Step 1: Review insert method steps

   Characters are added correctly, but after loop, isEndOfWord should be set true to mark word end.

2. Step 2: Identify missing line

   The comment '// Missing line here' indicates missing 'node.isEndOfWord = true;' which is essential.

3. Final Answer:

   The code does not mark the end of the word after insertion. -> Option A

4. Quick Check:

   Mark word end after insertion [OK]

Hint: Always set isEndOfWord true after inserting full word [OK]

Common Mistakes:

• Forgetting to mark end of word
• Confusing children structure with Map vs object
• Assuming constructor bug without checking insert

5. You want to find all words in a large dictionary that start with the prefix 'pro'. Which data structure is best and why? const words = ['program', 'progress', 'promise', 'problem', 'profile', 'project'];

hard

A. Use a Trie because it can quickly find all words with the prefix 'pro' without checking every word.

B. Use a Hash Map because it stores words as keys and can find prefixes instantly.

C. Use an array and filter words starting with 'pro' for best performance.

D. Use a linked list to store words and traverse to find prefix matches.

Solution

1. Step 1: Understand prefix search requirement

   Finding all words starting with 'pro' means searching by prefix efficiently.

2. Step 2: Compare data structures

   Trie stores words character by character, allowing fast prefix traversal. Hash Map and array require checking all words, linked list is slow.

3. Final Answer:

   Use a Trie because it can quickly find all words with the prefix 'pro' without checking every word. -> Option A

4. Quick Check:

   Prefix search = Trie best [OK]

Hint: Prefix search? Choose Trie for fast lookup [OK]

Common Mistakes:

• Thinking Hash Map supports prefix search efficiently
• Choosing array filter for large datasets
• Using linked list for prefix search