Prefix Search Using Trie in DSA Typescript - Execution Trace

Concept Flow - Prefix Search Using Trie

Start at root node

↓

For each char in prefix

↓

Check if char exists in current node children?

No→Prefix not found

Yes↓

Move to child node

↓

After last char, collect all words below

↓

Return list of words with prefix

Start from the root and follow each character of the prefix down the trie. If any character is missing, prefix is not found. Otherwise, collect all words below the last node.

Execution Sample

DSA Typescript

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

// Insert 'cat', 'car', 'dog'
// Search prefix 'ca'

This code inserts words into a trie and then searches for all words starting with prefix 'ca'.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat' char 'c'	root -> c	current = root.children.get('c') created	root └─ c
2	Insert 'cat' char 'a'	root -> c -> a	current = c.children.get('a') created	root └─ c └─ a
3	Insert 'cat' char 't'	root -> c -> a -> t (isWord=true)	current = a.children.get('t') created, mark isWord	root └─ c └─ a └─ t*
4	Insert 'car' char 'c'	root -> c -> a -> t*	current = root.children.get('c') exists	root └─ c └─ a └─ t*
5	Insert 'car' char 'a'	root -> c -> a -> t*	current = c.children.get('a') exists	root └─ c └─ a └─ t*
6	Insert 'car' char 'r'	root -> c -> a -> t*, r (isWord=true)	current = a.children.get('r') created, mark isWord	root └─ c └─ a ├─ t* └─ r*
7	Insert 'dog' char 'd'	root -> c -> a -> t*, r*; d	current = root.children.get('d') created	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d
8	Insert 'dog' char 'o'	root -> c -> a -> t*, r*; d -> o	current = d.children.get('o') created	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d └─ o
9	Insert 'dog' char 'g'	root -> c -> a -> t*, r*; d -> o -> g (isWord=true)	current = o.children.get('g') created, mark isWord	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d └─ o └─ g*
10	Search prefix 'ca' char 'c'	Same as above	current = root.children.get('c')	root └─ c (current)
11	Search prefix 'ca' char 'a'	Same as above	current = c.children.get('a')	root └─ c └─ a (current)
12	Collect words below 'a'	Same as above	Traverse children t*, r*	Words found: 'cat', 'car'

💡 Prefix 'ca' fully matched; collected words 'cat' and 'car' from trie nodes.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 11	Final
current	root	node 't' (end of 'cat')	node 'r' (end of 'car')	node 'g' (end of 'dog')	node 'a' (prefix end)	node 'a'
Trie Size	0	1 word inserted	2 words inserted	3 words inserted	3 words inserted	3 words inserted
Words Found	[]	[]	[]	[]	[]	['cat', 'car']

Key Moments - 3 Insights

Why do we mark isWord only at the last character node?

Because only the last character node represents a complete word. See execution_table rows 3, 6, and 9 where isWord is set.

What happens if a prefix character is missing in children?

The search stops immediately and returns no words. See execution_table row 11 where each prefix char must exist.

How do we collect all words after matching prefix?

We traverse all child nodes recursively from the prefix end node to find nodes marked isWord. See execution_table row 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which new node is created?

A Node 'r' under 'a'

B Node 't' under 'a'

C Node 'd' under root

D Node 'g' under 'o'

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 6.

At which step does the prefix search reach the node for 'a'?

A Step 10

B Step 12

C Step 11

D Step 9

💡 Hint

Look at the 'Pointer Changes' column for prefix search steps.

If we searched prefix 'do', what would be the pointer position after matching?

A Node 'd'

B Node 'o'

C Node 'g'

D Root node

💡 Hint

Follow the prefix characters in the trie from root to children as shown in execution_table steps 7-9.

Concept Snapshot

Prefix Search Using Trie:
- Start at root node
- For each prefix char, move to child node if exists
- If missing, prefix not found
- After last char, collect all words below
- Words are nodes marked isWord
- Efficient for prefix-based word search

Full Transcript

This visualization shows how prefix search works using a trie data structure. We insert words by creating nodes for each character and marking the last node as a word end. To search a prefix, we start at the root and follow each character down the trie. If any character is missing, the prefix does not exist. Otherwise, after the last prefix character, we collect all words below by traversing child nodes marked as word ends. The execution table traces insertion of 'cat', 'car', and 'dog', then searches prefix 'ca' and collects 'cat' and 'car'. The variable tracker shows pointer positions and words found at each step. Key moments clarify why isWord is marked only at word ends, what happens if prefix chars are missing, and how word collection works. The quiz tests understanding of node creation, pointer positions during search, and prefix traversal.

Practice

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

easy

A. To efficiently find all words that start with a given prefix

B. To sort words alphabetically

C. To store words in reverse order

D. To count the total number of words

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by their prefixes, allowing quick prefix-based lookups.

2. Step 2: Identify prefix search goal

   Prefix search means finding all words starting with a given prefix efficiently.

3. Final Answer:

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

4. Quick Check:

   Trie = Prefix search [OK]

Hint: Trie is built for prefix-based fast word retrieval [OK]

Common Mistakes:

• Confusing Trie with sorting structure
• Thinking Trie stores words reversed
• Assuming Trie counts total words only

2. Which of the following is the correct TypeScript syntax to define a Trie node with children as a Map and an endOfWord boolean?

easy

A. class TrieNode { children: object; endOfWord: string; constructor() { this.children = {}; this.endOfWord = ''; } }

B. class TrieNode { children: string[]; endOfWord: boolean; constructor() { this.children = []; this.endOfWord = false; } }

C. class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } }

D. class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } }

Solution

1. Step 1: Check children type

   Children should be a Map with string keys and TrieNode values for prefix characters.

2. Step 2: Check endOfWord type

   endOfWord is a boolean indicating if node ends a word.

3. Final Answer:

   class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } } -> Option D

4. Quick Check:

   Map + boolean endOfWord = class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } } [OK]

Hint: Use Map for children and boolean for endOfWord [OK]

Common Mistakes:

• Using array instead of Map for children
• Using wrong key type in Map
• Setting endOfWord as string instead of boolean

3. Given the following TypeScript code snippet, what will be the output of console.log(trie.startsWith('app'))?

class TrieNode {
  children = new Map();
  endOfWord = 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.endOfWord = 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');
trie.insert('bat');

medium

A. true

B. false

C. undefined

D. Error at runtime

Solution

1. Step 1: Insert words into Trie

   Words 'apple', 'app', and 'bat' are inserted, so prefix 'app' exists in Trie.

2. Step 2: Check startsWith method

   Method returns true if prefix characters exist in Trie nodes, which they do for 'app'.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Prefix 'app' found = true [OK]

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

Common Mistakes:

• Confusing startsWith with search for whole word
• Expecting false if prefix is a word itself
• Thinking startsWith returns endOfWord status

4. The following TypeScript code tries to implement a startsWith method for a Trie but always returns false. What is the bug?

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 false;
}

medium

A. It should check endOfWord before returning

B. It should use a for loop with index instead of for-of

C. It should return true after the loop if prefix exists

D. It should initialize node with a new TrieNode

Solution

1. Step 1: Analyze loop behavior

   The loop correctly traverses nodes for each prefix character.

2. Step 2: Check return statement

   Method returns false always after loop, so never returns true even if prefix found.

3. Step 3: Fix return logic

   Return true after loop if all prefix chars found.

4. Final Answer:

   It should return true after the loop if prefix exists -> Option C

5. Quick Check:

   Return true after loop if prefix found [OK]

Hint: Return true after loop if prefix nodes exist [OK]

Common Mistakes:

• Returning false at end regardless
• Checking endOfWord unnecessarily
• Incorrect node initialization

5. You want to extend a Trie to return all words starting with a given prefix. Which approach correctly implements this in TypeScript? A) Traverse to prefix node, then recursively collect all words below. B) Store all words in an array and filter by prefix each time. C) Use a hash map to map prefixes to words directly. D) Insert reversed words and search suffixes instead.

hard

A. Store all words in an array and filter by prefix each time.

B. Traverse to prefix node, then recursively collect all words below.

C. Use a hash map to map prefixes to words directly.

D. Insert reversed words and search suffixes instead.

Solution

1. Step 1: Understand prefix search extension

   To get all words with prefix, first find node matching prefix.

2. Step 2: Collect words recursively

   From prefix node, recursively traverse children to collect all complete words.

3. Step 3: Evaluate other options

   Filtering array or hash map is less efficient; reversed words search suffixes, not prefixes.

4. Final Answer:

   Traverse to prefix node, then recursively collect all words below. -> Option B

5. Quick Check:

   Recursive traversal from prefix node = Traverse to prefix node, then recursively collect all words below. [OK]

Hint: Find prefix node, then DFS to collect words [OK]

Common Mistakes:

• Filtering all words each time (slow)
• Using hash map without prefix traversal
• Confusing prefix with suffix search