Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Javascript - Quick Recap

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure that stores strings by sharing common prefixes. Each node represents a character, and paths from root to leaves form words.

beginner

Why can't a Hash Map efficiently handle prefix searches on strings?

Hash Maps store keys independently and do not share prefixes. So, searching for all keys with a common prefix requires checking every key, which is slow.

intermediate

How does a Trie improve prefix search compared to a Hash Map?

Trie nodes share prefixes, so searching for all words with a prefix is fast by following the prefix path once, then exploring its subtree.

beginner

What is a real-life example where Trie is better than Hash Map for strings?

Autocomplete in search engines: Trie quickly finds all words starting with typed letters, while Hash Map would check all stored words.

intermediate

What is a limitation of Hash Maps when storing many strings with shared prefixes?

Hash Maps store each string separately, wasting space by repeating prefixes, while Trie stores shared prefixes once, saving memory.

What does a Trie node typically represent?

A A character in a string

B A whole string

C A number

D A hash value

Each Trie node represents a single character, building strings by connecting nodes.

Why is prefix search slow in a Hash Map?

A Because Hash Maps use linked lists

B Because Hash Maps share prefixes

C Because Hash Maps store keys as trees

D Because Hash Maps do not store keys in order

Hash Maps store keys independently without order or prefix sharing, so prefix search requires checking all keys.

Which data structure is best for autocomplete features?

A Queue

B Trie

C Stack

D Hash Map

Trie efficiently finds all words with a given prefix, ideal for autocomplete.

How does Trie save memory compared to Hash Map for many strings with shared prefixes?

A By storing shared prefixes once

B By hashing prefixes

C By compressing strings

D By storing strings in arrays

Trie nodes represent shared prefixes once, reducing repeated storage.

Which operation is faster in Trie than in Hash Map?

A Inserting a number

B Finding a string by exact key

C Finding all strings with a given prefix

D Deleting a node

Trie is optimized for prefix searches, unlike Hash Map.

Explain why Trie is used for string prefix searches instead of Hash Maps.

Think about how strings share beginnings and how each data structure stores keys.

Describe a real-world scenario where Trie is better than Hash Map for handling strings.

Consider typing in a search box and how suggestions appear quickly.

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