Prefix Search Using Trie in DSA Javascript - Execution Trace

Concept Flow - Prefix Search Using Trie

Start at root node

↓

For each character in prefix

↓

Check if character exists in current node's children

↓

Move to child node

↓

After last character

↓

Collect all words below current node

↓

Return list of words with prefix

Start from the root, follow each prefix character down the trie nodes. If all prefix chars exist, collect all words below that node.

Execution Sample

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.endOfWord = 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.endOfWord = true;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) {
        return [];
      }
      node = node.children[char];
    }
    return this.collectAllWords(node, prefix);
  }

  collectAllWords(node, prefix) {
    let words = [];
    if (node.endOfWord) words.push(prefix);
    for (const char in node.children) {
      words = words.concat(this.collectAllWords(node.children[char], prefix + char));
    }
    return words;
  }
}

const trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("cart");
trie.insert("dog");
const result = trie.startsWith("car");
console.log(result);

This code inserts words into a trie and searches for words starting with 'car'.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat'	root -> c -> a -> t (endOfWord=true)	node moves from root to c, then a, then t	root └─ c └─ a └─ t*
2	Insert 'car'	root -> c -> a -> t (endOfWord=true), r (endOfWord=true)	node moves from root to c, then a, then adds r	root └─ c └─ a ├─ t* └─ r*
3	Insert 'cart'	root -> c -> a -> t (endOfWord=true), r -> t (endOfWord=true)	node moves from root to c, then a, then r, then adds t	root └─ c └─ a ├─ t* └─ r └─ t*
4	Insert 'dog'	root -> c -> a -> t (endOfWord=true), r -> t (endOfWord=true), d -> o -> g (endOfWord=true)	node moves from root to d, then o, then g	root ├─ c │ └─ a │ ├─ t* │ └─ r │ └─ t* └─ d └─ o └─ g*
5	Search prefix 'car'	Same as above	node moves root -> c -> a -> r	At node 'r' (endOfWord=true), collect words
6	Collect words under 'r'	Same as above	collect 'car' (endOfWord true), then 'cart' (from child t)	Words found: ['car', 'cart']
7	Return result	Same as above	No pointer moves	Output: ['car', 'cart']
8	End	No changes	No pointer moves	Search complete

💡 Search ends after collecting all words under prefix node 'r'

Variable Tracker

Variable	Start	After Insert 'cat'	After Insert 'car'	After Insert 'cart'	After Insert 'dog'	After Search 'car'	Final
node	root	points to 't' node of 'cat'	points to 'r' node of 'car'	points to 't' node of 'cart'	points to 'g' node of 'dog'	points to 'r' node of prefix 'car'	points to 'r' node of prefix 'car'
trie.root.children	{}	{c: TrieNode}	{c: TrieNode}	{c: TrieNode}	{c: TrieNode, d: TrieNode}	{c: TrieNode, d: TrieNode}	{c: TrieNode, d: TrieNode}
collectedWords	[]	[]	[]	[]	[]	['car', 'cart']	['car', 'cart']

Key Moments - 3 Insights

Why do we stop searching if a character in the prefix is not found in children?

Because as shown in execution_table step 5, if any prefix character is missing, the search returns empty immediately since no words can have that prefix.

How do we collect all words after reaching the prefix node?

As in step 6, we recursively visit all child nodes from the prefix node, adding words when endOfWord is true, collecting all matching words.

Why do we mark endOfWord at the last character node during insertion?

Marking endOfWord (steps 1-4) tells us which nodes represent complete words, so during collection we know which prefixes form valid words.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which node does the pointer 'node' point to after searching prefix 'car'?

A Root node

B Node 't' under 'a'

C Node 'r' under 'a'

D Node 'o' under 'd'

💡 Hint

Check execution_table row 5 under 'Pointer Changes' and 'Visual State'

At which step does the trie first contain the word 'dog'?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at execution_table rows and see when 'd -> o -> g' nodes appear

If we search prefix 'ca' instead of 'car', how would the collected words change?

A It would return ['cat', 'car', 'cart']

B It would return ['car', 'cart'] only

C It would return ['cat'] only

D It would return []

💡 Hint

Refer to how collection works from prefix node in execution_table step 6

Concept Snapshot

Prefix Search Using Trie:
- Start at root node
- Follow each prefix character down children
- If any char missing, return empty list
- After last prefix char, collect all words below
- Use endOfWord flag to identify complete words
- Returns all words starting with given prefix

Full Transcript

This visualization shows how prefix search works in a trie. We start at the root and follow each character of the prefix down the trie nodes. If any character is missing, we stop and return no words. If all prefix characters are found, we collect all words below that node by recursively visiting children nodes and checking the endOfWord flag. The example inserts words 'cat', 'car', 'cart', and 'dog' into the trie, then searches for words starting with 'car', returning ['car', 'cart']. The execution table tracks each insertion and the search steps, showing how nodes and pointers change. The variable tracker shows how the current node pointer moves and how collected words build up. Key moments clarify why we stop early if prefix chars are missing, how collection works, and why endOfWord is important. The quiz tests understanding of pointer positions, insertion steps, and collection results. This method efficiently finds all words sharing a prefix in a set of strings.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To efficiently find all words starting with a given prefix

B. To sort words alphabetically

C. To store numbers in ascending order

D. To perform arithmetic operations quickly

Solution

1. Step 1: Understand Trie usage

   A Trie stores words in a tree-like structure where each node represents a character.

2. Step 2: Identify prefix search benefit

   This structure allows quick traversal to find all words sharing a prefix without scanning all words.

3. Final Answer:

   To efficiently find all words starting with a given prefix -> Option A

4. Quick Check:

   Trie = prefix search efficiency [OK]

Hint: Trie nodes represent characters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie stores numbers only
• Assuming Trie is for arithmetic

2. Which of the following is the correct way to initialize an empty Trie node in JavaScript?

easy

A. const node = [];

B. const node = new Map();

C. const node = null;

D. const node = { children: {}, isEnd: false };

Solution

1. Step 1: Understand Trie node structure

   A Trie node typically has a children object to hold next characters and a boolean to mark word end.

2. Step 2: Match correct initialization

   const node = { children: {}, isEnd: false }; correctly creates an object with children as empty object and isEnd as false.

3. Final Answer:

   const node = { children: {}, isEnd: false }; -> Option D

4. Quick Check:

   Trie node = object with children and isEnd [OK]

Hint: Trie nodes use objects with children and end flag [OK]

Common Mistakes:

• Using array instead of object for children
• Setting node to null instead of object
• Using Map without isEnd flag

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

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = 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.isEnd = true;
  }
  startsWith(prefix) {
    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('cat');
trie.insert('car');
trie.insert('dog');
console.log(trie.startsWith('ca'));

medium

A. true

B. false

C. undefined

D. Error

Solution

1. Step 1: Insert words into Trie

   Words 'cat', 'car', and 'dog' are inserted, creating nodes for each character.

2. Step 2: Check prefix 'ca'

   Both 'cat' and 'car' start with 'ca', so traversal finds nodes for 'c' and 'a'.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Prefix 'ca' exists = true [OK]

Hint: If prefix matches inserted words, startsWith returns true [OK]

Common Mistakes:

• Confusing startsWith with exact word search
• Expecting false if prefix is partial
• Ignoring that multiple words share prefix

4. Identify the bug in the following Trie insert method and select the fix:

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.isEnd = true;
}

medium

A. Remove node.isEnd assignment

B. Change if condition to check if child does NOT exist before creating new node

C. Initialize node as null before loop

D. Use a Map instead of object for children

Solution

1. Step 1: Analyze insert method logic

   The code creates a new node only if node.children[char] exists, which is incorrect.

2. Step 2: Correct condition for node creation

   We should create a new node only if node.children[char] does NOT exist to avoid overwriting existing nodes.

3. Final Answer:

   Change if condition to check if child does NOT exist before creating new node -> Option B

4. Quick Check:

   Insert new node only if missing [OK]

Hint: Create new child node only if it does not exist [OK]

Common Mistakes:

• Creating new node when child already exists
• Forgetting to mark end of word
• Initializing node incorrectly

5. Given a list of words ['apple', 'app', 'apricot', 'banana'], how would you use a Trie to find all words starting with 'ap'? Choose the correct approach.

hard

A. Insert only words starting with 'ap' into Trie and ignore others

B. Sort the list and filter words starting with 'ap' using string methods

C. Insert all words into Trie, then traverse nodes for prefix 'ap' and collect all descendant words

D. Use a hash map to store words and check prefix by substring matching

Solution

1. Step 1: Build Trie with all words

   Insert all words so the Trie contains complete data for prefix search.

2. Step 2: Traverse Trie for prefix 'ap'

   Navigate nodes for 'a' then 'p', then collect all words from this subtree.

3. Step 3: Collect descendant words

   Gather words like 'apple', 'app', and 'apricot' that share the prefix.

4. Final Answer:

   Insert all words into Trie, then traverse nodes for prefix 'ap' and collect all descendant words -> Option C

5. Quick Check:

   Trie + prefix traversal = all matching words [OK]

Hint: Insert all words, then traverse prefix subtree to find matches [OK]

Common Mistakes:

• Filtering list without Trie defeats purpose
• Ignoring words not starting with prefix during insertion
• Using hash map instead of Trie for prefix search