Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Typescript - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why is a Trie preferred over a Hash Map for prefix searches?

Imagine you want to find all words starting with 'app' in a large dictionary. Why is a Trie better than a Hash Map for this task?

A Trie stores characters in a tree structure allowing efficient prefix search, while Hash Map cannot efficiently find keys by prefix.

B Hash Map uses less memory than Trie, so it is better for prefix searches.

C Trie is slower than Hash Map for prefix searches because it stores entire words.

D Hash Map can find prefixes faster because it hashes the prefix directly.

💡 Hint

Think about how each data structure organizes keys and how that affects searching by starting letters.

A Trie stores strings character by character in a tree, making it easy to find all words sharing a prefix by traversing the tree. A Hash Map stores whole keys and cannot efficiently find keys by partial prefixes.

❓ Predict Output

intermediate

Output of Trie prefix search vs Hash Map lookup

Given the following TypeScript code, what is the output?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isWord = false;
}

class Trie {
  root = new TrieNode();

  insert(word: string) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isWord = true;
  }

  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return false;
      node = node.children.get(char)!;
    }
    return true;
  }
}

const trie = new Trie();
trie.insert('apple');
trie.insert('app');

const hashMap = new Map<string, boolean>();
hashMap.set('apple', true);
hashMap.set('app', true);

console.log(trie.startsWith('app'));
console.log(hashMap.has('app'));
console.log(hashMap.has('ap'));
console.log(trie.startsWith('ap'));

A

true
true
false
true

B

true
true
true
true

C

false
true
false
false

D

true
false
false
true

💡 Hint

Check how Trie and Hash Map handle prefixes and exact keys differently.

Trie.startsWith('app') returns true because 'app' is a prefix in the Trie. Hash Map.has('app') returns true because 'app' is a key. Hash Map.has('ap') returns false because 'ap' is not a key. Trie.startsWith('ap') returns true because 'ap' is a prefix of inserted words.

🔧 Debug

advanced

Why does this Trie prefix search fail for some prefixes?

Find the bug in this TypeScript Trie startsWith method that causes it to return false for some prefixes that exist.

DSA Typescript

class TrieNode {
  children: {[key: string]: TrieNode} = {};
  isWord = false;
}

class Trie {
  root = new TrieNode();

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

  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true;
  }
}

const trie = new Trie();
trie.insert('hello');
console.log(trie.startsWith('hel'));

A The startsWith method should check for isWord at each character.

B The startsWith method incorrectly returns node.isWord instead of true after prefix traversal.

C The children property should be a Map instead of an object.

D The insert method does not add nodes for each character properly.

💡 Hint

Think about what startsWith should return after successfully finding the prefix path.

startsWith should return true if the prefix path exists, regardless of whether the prefix itself is a complete word. Returning node.isWord causes false for prefixes that are not complete words.

❓ Predict Output

advanced

Memory usage difference between Trie and Hash Map for many strings

Consider storing 1000 English words in a Trie and a Hash Map. Which statement about memory usage is true?

A Hash Map uses less memory because it stores only keys without extra nodes.

B Both use the same memory because they store all words fully.

C Trie uses less memory because it shares common prefixes among words.

D Trie uses more memory because it stores each character as a separate node.

💡 Hint

Think about how words with common beginnings are stored in each structure.

Trie shares nodes for common prefixes, reducing memory for overlapping parts. Hash Map stores each key fully, so it uses more memory when many words share prefixes.

🧠 Conceptual

expert

Why can't Hash Maps efficiently support autocomplete features like Tries?

Autocomplete requires finding all words starting with a prefix quickly. Why is a Trie better suited than a Hash Map for this feature?

A Hash Map automatically sorts keys, making prefix search faster than Trie.

B Hash Map can store prefixes as keys, so it is equally efficient as Trie for autocomplete.

C Trie is slower because it needs to check each character, while Hash Map hashes the prefix directly.

D Trie organizes words by characters allowing traversal to prefix node and collecting descendants; Hash Map lacks this structure and requires scanning all keys.

💡 Hint

Consider how each data structure organizes and accesses keys related by prefixes.

Trie nodes represent characters and link to children, so after reaching the prefix node, all words with that prefix are descendants. Hash Map stores keys independently, so finding all keys with a prefix requires checking every key, which is inefficient.

Practice

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

easy

A. Because Trie is faster for exact string lookups than Hash Maps

B. Because Trie uses less memory than a Hash Map for all cases

C. Because Hash Maps cannot store strings as keys

D. Because Trie efficiently supports prefix-based searches and auto-completion

Solution

1. Step 1: Understand Trie and Hash Map capabilities

   Trie stores strings in a tree form, allowing quick prefix searches. Hash Maps store keys but do not support prefix queries efficiently.

2. Step 2: Compare use cases for prefix search

   Trie can find all strings starting with a prefix quickly, which Hash Maps cannot do without scanning all keys.

3. Final Answer:

   Because Trie efficiently supports prefix-based searches and auto-completion -> Option D

4. Quick Check:

   Prefix search = Trie [OK]

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

Common Mistakes:

• Thinking Hash Maps support prefix search efficiently
• Assuming Trie always uses less memory
• Believing Hash Maps cannot store strings as keys

2. Which of the following is the correct TypeScript syntax to declare a Trie node with children as a Map of characters to nodes?

easy

A. class TrieNode { children: Map = new Map(); }

B. class TrieNode { children: Map = new Map(); }

C. class TrieNode { children: Map = new Map(); }

D. class TrieNode { children: Map = new Map(); }

Solution

1. Step 1: Understand Map type declaration in TypeScript

   Map keys and values must be typed as Map. Here keys are characters (string), values are TrieNode.

2. Step 2: Check each option's syntax

   class TrieNode { children: Map = new Map(); } correctly declares children as Map initialized with new Map(). Others have wrong generic order or types.

3. Final Answer:

   class TrieNode { children: Map = new Map(); } -> Option A

4. Quick Check:

   Map syntax correct [OK]

Hint: Map with correct order and initialization [OK]

Common Mistakes:

• Swapping key and value types in Map
• Not initializing Map with new Map()
• Using wrong generic types for Map

3. Given the following TypeScript Trie insertion code snippet, what will be the output after inserting words ['cat', 'car', 'dog'] and searching for prefix 'ca'?

class TrieNode {
  children: Map = new Map();
  isEnd: boolean = false;
}

class Trie {
  root = new TrieNode();

  insert(word: string) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
  }

  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch)!;
    }
    return true;
  }
}

const trie = new Trie();
['cat', 'car', 'dog'].forEach(w => trie.insert(w));
console.log(trie.startsWith('ca'));

medium

A. undefined

B. true

C. false

D. Error at runtime

Solution

1. Step 1: Insert words into Trie

   Words 'cat', 'car', and 'dog' are inserted. 'ca' prefix nodes are created for 'c' and 'a'.

2. Step 2: Check startsWith for 'ca'

   Traversal finds nodes for 'c' and 'a' successfully, so returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Prefix 'ca' exists = true [OK]

Hint: If prefix nodes exist, startsWith returns true [OK]

Common Mistakes:

• Confusing startsWith with exact word search
• Assuming isEnd must be true for prefix check
• Expecting false if prefix is partial

4. The following TypeScript Trie search method is intended to check if a word exists. What is the bug?

search(word: string): boolean {
  let node = this.root;
  for (const ch of word) {
    if (!node.children.has(ch)) return false;
    node = node.children.get(ch)!;
  }
  return false;
}

medium

A. It always returns false even if word exists

B. It throws an error when word is empty

C. It returns true for any prefix, not full word

D. It does not check if node is null

Solution

1. Step 1: Analyze the return statement after loop

   The method returns false after the loop without checking if the last node marks end of a word.

2. Step 2: Identify missing isEnd check

   It should return node.isEnd to confirm full word presence, not just prefix.

3. Final Answer:

   It always returns false even if word exists -> Option A

4. Quick Check:

   Missing isEnd check causes always false [OK]

Hint: Check isEnd after traversal to confirm full word [OK]

Common Mistakes:

• Returning false without checking isEnd
• Confusing prefix search with full word search
• Ignoring empty string edge case

5. You want to store a large dictionary of words and quickly find all words starting with a given prefix. Why is a Trie better than a Hash Map for this, and what is a limitation of Hash Map in this scenario?

hard

A. Trie uses less memory than Hash Map; Hash Map cannot store string keys longer than 10 characters.

B. Trie supports exact word search only; Hash Map supports prefix search but slower.

C. Trie stores words in a prefix tree allowing fast prefix queries; Hash Map can't efficiently find keys by prefix without scanning all keys.

D. Trie is slower for insertion; Hash Map is faster for prefix search.

Solution

1. Step 1: Understand Trie prefix storage

   Trie organizes words by shared prefixes in a tree, enabling quick retrieval of all words with a prefix.

2. Step 2: Understand Hash Map limitations

   Hash Map stores keys without order, so prefix search requires checking all keys, which is inefficient.

3. Final Answer:

   Trie stores words in a prefix tree allowing fast prefix queries; Hash Map can't efficiently find keys by prefix without scanning all keys. -> Option C

4. Quick Check:

   Prefix search efficiency = Trie advantage [OK]

Hint: Trie = fast prefix search; Hash Map = no prefix search [OK]

Common Mistakes:

• Thinking Hash Map supports prefix search efficiently
• Assuming Trie uses less memory always
• Confusing exact search with prefix search