Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Javascript - Why This Pattern

Mental Model

A trie stores words by their letters step-by-step, letting us find all words with the same start easily. Hash maps store whole words as keys, so they can't quickly find words sharing beginnings.

Analogy: Imagine a tree of roads where each letter is a turn. To find all houses on a street starting with 'cat', you just follow the road 'c' -> 'a' -> 't' and see all houses there. A hash map is like a list of full addresses; you can't find all houses on 'cat' street without checking every address.

root
 ↓
 c -> a -> t -> [end]
           ↓
           s -> [end]

Hash Map:
{
  "cat": true,
  "cats": true
}

Dry Run Walkthrough

Input: words: ["cat", "cats", "car"], find all words starting with "ca"

Goal: Show how trie quickly finds all words starting with "ca" while hash map cannot do this efficiently

Step 1: Insert "cat" into trie letter by letter

root -> c -> a -> t -> [end]

Why: We build the path for the word "cat" step by step

Step 2: Insert "cats" by extending from "cat" with letter 's'

root -> c -> a -> t -> s -> [end]

Why: Words sharing prefix reuse existing nodes, saving space

Step 3: Insert "car" branching from 'a' with letter 'r'

root -> c -> a -> t -> s -> [end]
               ↓
               r -> [end]

Why: Trie branches to represent different words sharing prefix

Step 4: Search prefix "ca" by following nodes 'c' then 'a'

root -> c -> a ↑

Why: We reach the node representing prefix "ca" to find all words starting with it

Step 5: Collect all words below node 'a': "cat", "cats", "car"

root -> c -> a -> t -> s -> [end]
               ↓
               r -> [end]

Why: Trie structure allows easy collection of all words sharing prefix

Result:

root -> c -> a -> t -> s -> [end]
               ↓
               r -> [end]
Words starting with "ca": "cat", "cats", "car"

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

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return [];
      }
      node = node.children.get(char); // advance node to prefix end
    }
    return this._collectAllWords(node, prefix);
  }

  _collectAllWords(node, prefix) {
    const words = [];
    if (node.isEnd) words.push(prefix); // add word if end reached
    for (const [char, childNode] of node.children) {
      words.push(...this._collectAllWords(childNode, prefix + char)); // recurse children
    }
    return words;
  }
}

// Driver code
const trie = new Trie();
const words = ["cat", "cats", "car"];
for (const word of words) {
  trie.insert(word);
}
const prefix = "ca";
const result = trie.startsWith(prefix);
console.log(`Words starting with "${prefix}": ${result.join(", ")}`);

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

advance node to next letter node to build or traverse word

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

mark current node as end of a valid word

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

traverse trie nodes to reach prefix end

if (node.isEnd) words.push(prefix); // add word if end reached

collect word if current node marks word end

words.push(...this._collectAllWords(childNode, prefix + char)); // recurse children

recursively collect all words under current node

Output

Words starting with "ca": cat, cats, car

Complexity Analysis

Time: O(m + n) where m is prefix length and n is total letters in subtree because we traverse prefix then collect all words

Space: O(n) for storing all nodes and collected words in recursion

vs Alternative: Hash map lookup is O(1) for full words but cannot efficiently find all words sharing a prefix without scanning all keys, which is O(k) where k is number of keys

Edge Cases

Empty prefix search

Returns all words in trie because prefix is empty

DSA Javascript

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

Prefix not in trie

Returns empty list because prefix path does not exist

DSA Javascript

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

Insert duplicate word

Marks same end node again, no duplicate nodes created

DSA Javascript

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

When to Use This Pattern

When you need to find all words sharing a prefix quickly, reach for the trie pattern because hash maps cannot efficiently handle prefix searches.

Common Mistakes

Mistake: Trying to use hash map keys to find prefix matches by scanning all keys
Fix: Use a trie to store words letter by letter so prefix traversal is direct and efficient

Summary

A trie stores words letter by letter to enable fast prefix searches.

Use a trie when you need to find or autocomplete words sharing the same start.

The key insight is that tries share common prefixes as shared paths, unlike hash maps that treat words as separate keys.

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