Trie vs Hash Map for Prefix Matching in DSA Javascript - Trade-offs & Analysis

Mental Model

A trie stores words by their letters in a tree, making prefix search fast. A hash map stores whole words as keys, so prefix search needs extra work.

Analogy: Imagine a phone book organized by first letter, then second letter, and so on (trie), versus a list of full names where you have to check each name to find those starting with a prefix (hash map).

Trie:
root
 ├─ a
 │   ├─ p
 │   │   ├─ p
 │   │   │   └─ l
 │   │   │       └─ e (end)
 └─ b
     └─ a
         └─ t (end)

Hash Map:
{
  "apple": true,
  "bat": true
}

Dry Run Walkthrough

Input: words: ["apple", "bat"], prefix to search: "ap"

Goal: Find if any word starts with prefix "ap" using trie and hash map

Step 1: Insert "apple" into trie by creating nodes for each letter

root -> a -> p -> p -> l -> e [end]
Hash Map: {"apple": true}

Why: Build trie structure to represent "apple" letter by letter

Step 2: Insert "bat" into trie by creating nodes for each letter

root -> a -> p -> p -> l -> e [end]
      └─ b -> a -> t [end]
Hash Map: {"apple": true, "bat": true}

Why: Add second word to trie sharing no prefix with "apple"

Step 3: Search prefix "ap" in trie by following nodes a -> p

At node p after root -> a -> p
Hash Map keys: ["apple", "bat"]

Why: Traverse trie nodes matching prefix letters

Step 4: Confirm prefix exists in trie since nodes for 'a' and 'p' found

Prefix "ap" found in trie
Hash Map: Need to check keys for prefix

Why: Trie structure directly shows prefix presence

Step 5: Search prefix "ap" in hash map by checking each key

Check "apple" starts with "ap" -> true
Check "bat" starts with "ap" -> false

Why: Hash map requires scanning keys for prefix match

Step 6: Return true for prefix found in both trie and hash map

Result: prefix "ap" exists

Why: Both data structures confirm prefix presence

Result:

Trie:
root -> a -> p -> p -> l -> e [end]
      └─ b -> a -> t [end]
Prefix "ap" found
Hash Map: {"apple": true, "bat": true}
Prefix "ap" found by scanning keys

Annotated Code

DSA Javascript

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

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

  insert(word) {
    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); // advance to child node
    }
    node.isEnd = true; // mark end of word
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return false; // prefix not found
      }
      node = node.children.get(char); // advance to next node
    }
    return true; // prefix found
  }
}

// Hash Map prefix search
function hashMapPrefixSearch(map, prefix) {
  for (const key of map.keys()) {
    if (key.startsWith(prefix)) {
      return true; // prefix found
    }
  }
  return false; // prefix not found
}

// Driver code
const words = ["apple", "bat"];
const prefix = "ap";

// Build trie
const trie = new Trie();
for (const word of words) {
  trie.insert(word);
}

// Build hash map
const map = new Map();
for (const word of words) {
  map.set(word, true);
}

// Search prefix
console.log("Trie prefix found:", trie.startsWith(prefix));
console.log("Hash Map prefix found:", hashMapPrefixSearch(map, prefix));

node = node.children.get(char); // advance to child node

advance node to next letter node to build or traverse trie

node.isEnd = true; // mark end of word

mark current node as end of a valid word

if (!node.children.has(char)) { return false; }

stop search if prefix letter missing in trie

for (const key of map.keys()) { if (key.startsWith(prefix)) { return true; } }

scan all keys in hash map to find prefix match

Output

Trie prefix found: true

Hash Map prefix found: true

Complexity Analysis

Time: Trie prefix search: O(m) where m is prefix length, because we follow nodes letter by letter. Hash map prefix search: O(n * m) where n is number of keys and m is prefix length, because we check each key's start.

Space: Trie uses O(total letters in all words) for nodes, which can be less if words share prefixes. Hash map uses O(n) for storing all words as keys.

vs Alternative: Trie is faster for prefix queries because it avoids scanning all keys, while hash map requires checking each key, making it slower for large datasets.

Edge Cases

Empty prefix string

Trie returns true immediately since empty prefix matches all words; hash map also returns true since all keys start with empty string

DSA Javascript

for (const char of prefix) { if (!node.children.has(char)) { return false; } }

Prefix not present in any word

Trie returns false when missing node found; hash map returns false after scanning all keys

DSA Javascript

if (!node.children.has(char)) { return false; }

Words with shared prefixes

Trie nodes are shared, saving space and speeding prefix search; hash map stores all keys separately

DSA Javascript

node = node.children.get(char);

When to Use This Pattern

When you need to quickly find if any word starts with a given prefix, especially in large word sets, reach for the trie pattern because it allows fast prefix traversal without scanning all words.

Common Mistakes

Mistake: Trying to do prefix search directly on hash map keys without scanning all keys
Fix: Implement a loop to check each key's start or use a trie for efficient prefix queries

Mistake: Not marking end of word in trie, causing incorrect prefix or word detection
Fix: Set isEnd = true at the last node of inserted word

Summary

Compares trie and hash map for checking if any word starts with a prefix.

Use trie for efficient prefix search in large word collections; hash map is simpler but slower for prefix queries.

Trie stores words letter by letter in a tree, enabling fast prefix traversal without scanning all words.

Practice

1. Which data structure is generally more efficient for prefix matching in a large set of strings?

easy

A. Linked List, because it allows sequential access

B. Hash Map, because it stores keys with constant time lookup

C. Array, because it stores elements in order

D. Trie, because it stores prefixes explicitly and allows fast prefix search

Solution

1. Step 1: Understand prefix matching requirement

   Prefix matching means finding all strings that start with a given prefix efficiently.

2. Step 2: Compare Trie and Hash Map for prefix search

   Trie stores prefixes explicitly, allowing quick traversal to all words with that prefix. Hash Map does not store prefixes, so it requires checking all keys or additional structures.

3. Final Answer:

   Trie, because it stores prefixes explicitly and allows fast prefix search -> Option D

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Trie stores prefixes explicitly, ideal for prefix search [OK]

Common Mistakes:

• Thinking hash map can do prefix search directly
• Confusing prefix matching with exact key lookup
• Assuming arrays or linked lists are efficient for prefix search

2. Which of the following is the correct way to check if a prefix exists in a Trie node in JavaScript?

easy

A. if (prefix in trieNode) { ... }

B. if (trieNode.hasOwnProperty(prefix)) { ... }

C. if (trieNode[prefix]) { ... }

D. if (trieNode.contains(prefix)) { ... }

Solution

1. Step 1: Understand how to check keys in JavaScript objects

   The 'in' operator checks if a property exists in an object or its prototype chain.

2. Step 2: Compare options for checking prefix in Trie node

   if (prefix in trieNode) { ... } uses 'prefix in trieNode', which correctly checks if the prefix key exists. if (trieNode.hasOwnProperty(prefix)) { ... } uses hasOwnProperty which is valid but less common for prefix check. if (trieNode[prefix]) { ... } checks truthiness which can fail if value is falsy. if (trieNode.contains(prefix)) { ... } uses a non-existent method.

3. Final Answer:

   if (prefix in trieNode) { ... } -> Option A

4. Quick Check:

   Use 'in' operator to check keys [OK]

Hint: Use 'in' operator to check keys in objects [OK]

Common Mistakes:

• Using non-existent 'contains' method
• Checking property truthiness instead of existence
• Confusing hasOwnProperty with 'in' operator

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

const trie = {};
function insert(word) {
  let node = trie;
  for (const char of word) {
    if (!(char in node)) node[char] = {};
    node = node[char];
  }
  node.isEnd = true;
}

insert('cat');
insert('car');
insert('dog');

console.log('c' in trie, 'a' in trie['c'], 't' in trie['c']['a'], trie['c']['a']['t'].isEnd);

medium

A. true true true true

B. true true false undefined

C. true false false undefined

D. false false false undefined

Solution

1. Step 1: Trace insertions of words into the trie

   Inserting 'cat' creates nodes c -> a -> t with isEnd true at 't'. Inserting 'car' adds r under c -> a. Inserting 'dog' adds d -> o -> g separately.

2. Step 2: Check existence of keys and isEnd property

   'c' exists in trie, 'a' exists under 'c', 't' exists under 'a', and 't' node has isEnd true from 'cat' insertion.

3. Final Answer:

   true true true true -> Option A

4. Quick Check:

   All keys and isEnd exist as expected [OK]

Hint: Trace each insertion step-by-step [OK]

Common Mistakes:

• Assuming 't' node missing after insertions
• Confusing isEnd property placement
• Not updating node reference inside loop

4. The following code attempts to check if a prefix exists in a Trie but does not work correctly. What is the bug?

function startsWith(trie, prefix) {
  let node = trie;
  for (const char of prefix) {
    if (!node[char]) return false;
    node = node[char];
  }
  return true;
}

medium

A. It incorrectly returns false if a node exists but is falsy

B. It does not check if the prefix is a complete word

C. It should use 'char in node' instead of '!node[char]'

D. It does not handle empty prefix input

Solution

1. Step 1: Analyze the condition '!node[char]'

   This condition fails if node[char] exists but is falsy (like an empty object or false), causing incorrect false return.

2. Step 2: Suggest correct key existence check

   Using 'char in node' correctly checks if the key exists regardless of value truthiness.

3. Final Answer:

   It should use 'char in node' instead of '!node[char]' -> Option C

4. Quick Check:

   Use 'in' operator to check keys, not truthiness [OK]

Hint: Check key existence with 'in', not truthiness [OK]

Common Mistakes:

• Using falsy check instead of key existence
• Confusing prefix existence with complete word check
• Ignoring empty prefix edge case

5. You want to implement a prefix search that returns all words starting with a given prefix from a large dictionary. Which approach is best and why?

// Approach 1: Use a Hash Map storing all words as keys
// Approach 2: Use a Trie storing words character by character
// Approach 3: Use an array and filter words by prefix
// Approach 4: Use a sorted array and binary search for prefix

hard

A. Approach 4, because binary search on sorted array quickly finds prefix range

B. Approach 2, because Trie allows efficient prefix traversal and retrieval

C. Approach 3, because filtering arrays is simple and fast for large data

D. Approach 1, because Hash Map has constant time lookup for prefixes

Solution

1. Step 1: Evaluate each approach for prefix search

   Hash Map (Approach 1) cannot do prefix search efficiently as keys are exact. Array filter (Approach 3) is slow for large data. Sorted array with binary search (Approach 4) helps but retrieving all matches requires scanning range.

2. Step 2: Understand Trie advantages

   Trie (Approach 2) stores prefixes explicitly, allowing fast traversal to all words sharing the prefix, making it best for prefix search in large datasets.

3. Final Answer:

   Approach 2, because Trie allows efficient prefix traversal and retrieval -> Option B

4. Quick Check:

   Prefix search efficiency = Trie [OK]

Hint: Trie stores prefixes explicitly, best for prefix search [OK]

Common Mistakes:

• Assuming hash map supports prefix search
• Ignoring performance cost of filtering large arrays
• Overestimating binary search for prefix retrieval