Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Javascript - Why It Works

Concept Flow - Why Trie Exists and What Hash Map Cannot Do for Strings

Start with empty Trie

↓

Insert word letter by letter

↓

Create nodes for letters if missing

↓

Mark end of word

↓

Search prefix by traversing nodes

↓

Find all words with prefix

↓

Store whole word as key

↓

Cannot find words by prefix efficiently

Trie stores words letter by letter, enabling fast prefix search, unlike hash maps that store whole words and can't efficiently find prefixes.

Execution Sample

DSA Javascript

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

Defines a Trie node with children links and end-of-word marker.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat' letter 'c'	Root	Create node for 'c' under root	root -> c
2	Insert 'cat' letter 'a'	root -> c	Create node for 'a' under 'c'	root -> c -> a
3	Insert 'cat' letter 't'	root -> c -> a	Create node for 't' under 'a'	root -> c -> a -> t (isEnd=true)
4	Insert 'car' letter 'c'	root -> c -> a -> t	Node 'c' exists, move to 'c'	root -> c -> a -> t
5	Insert 'car' letter 'a'	root -> c -> a -> t	Node 'a' exists under 'c', move to 'a'	root -> c -> a -> t
6	Insert 'car' letter 'r'	root -> c -> a -> t	Create node for 'r' under 'a'	root -> c -> a -> {t, r (isEnd=true)}
7	Search prefix 'ca'	root -> c -> a -> {t, r}	Traverse nodes 'c' then 'a'	At node 'a', prefix found
8	Find words with prefix 'ca'	root -> c -> a -> {t, r}	Collect words 'cat' and 'car'	Words: 'cat', 'car'
9	Hash Map stores 'cat' and 'car' as keys	Keys: 'cat', 'car'	No prefix traversal possible	Cannot find all words starting with 'ca' efficiently

💡 All words inserted and prefix search demonstrated; hash map cannot do prefix search efficiently.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	After Step 8
Trie Nodes	{}	{c: {}}	{c: {a: {t: {isEnd: true}}}}	{c: {a: {t: {isEnd: true}, r: {isEnd: true}}}}	{c: {a: {t: {isEnd: true}, r: {isEnd: true}}}}
Current Pointer	root	node at 'c'	node at 't'	node at 'r'	node at 'a' (prefix node)
Words Found	[]	[]	[]	[]	['cat', 'car']

Key Moments - 3 Insights

Why can't a hash map efficiently find all words with a given prefix?

Because hash maps store whole words as keys, they cannot traverse letter by letter to find prefixes. The execution_table row 9 shows hash map keys and notes no prefix traversal.

Why does Trie create nodes for each letter instead of storing whole words?

Trie stores words letter by letter to share common prefixes, saving space and enabling prefix search. See execution_table steps 1-6 where nodes are created per letter.

How does Trie mark the end of a word?

Trie uses a boolean flag 'isEnd' at the last letter node of a word. Execution_table step 3 and 6 show nodes with isEnd=true.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what nodes exist under 'a'?

A Nodes 't' and 'r' with isEnd true on 'r'

B Only node 't' with isEnd true

C Nodes 't' and 'r' with isEnd true on both

D No nodes under 'a'

💡 Hint

Check execution_table row 6 under Visual State column

At which step does the Trie mark the end of the word 'cat'?

A Step 1

B Step 6

C Step 3

D Step 9

💡 Hint

Look at execution_table rows 3 and 6 for isEnd flags

If we want to find all words starting with 'ca', which data structure allows efficient search?

A Hash Map

B Trie

C Array

D Stack

💡 Hint

Refer to execution_table rows 7 and 8 showing prefix search

Concept Snapshot

Trie stores words letter by letter in nodes.
Each node links to next letters.
Marks end of word with a flag.
Enables fast prefix search.
Hash maps store whole words, no prefix traversal.
Trie saves space by sharing prefixes.

Full Transcript

Trie is a tree-like data structure that stores words letter by letter. Each node represents a letter and links to child nodes for next letters. When inserting a word, Trie creates nodes for letters if missing and marks the last letter node as end of word. This structure allows fast searching of prefixes by traversing nodes letter by letter. Hash maps store whole words as keys and cannot efficiently find all words sharing a prefix. The execution trace shows inserting 'cat' and 'car' into Trie, marking end nodes, and searching prefix 'ca' to find both words. Hash map stores keys 'cat' and 'car' but cannot do prefix search efficiently. This explains why Trie exists and what hash maps cannot do for strings.

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