Word Search in Trie in DSA Typescript - Execution Trace

Concept Flow - Word Search in Trie

Start at root node

↓

Check first letter of word

↓

Letter found in children?

No→Word NOT found

Yes↓

Move to child node

↓

More letters?

Yes→Repeat check for next letter

No↓

Is current node end of word?

Yes→Word FOUND

No↓

Word NOT found

Start from the root and check each letter of the word in the trie nodes. If all letters match and the last node marks end of a word, the word is found.

Execution Sample

DSA Typescript

function searchWord(root: TrieNode, word: string): boolean {
  let current = root;
  for (const char of word) {
    if (!current.children.has(char)) return false;
    current = current.children.get(char)!;
  }
  return current.isEndOfWord;
}

This code checks each letter of the word in the trie nodes and returns true if the word exists.

Execution Table

Step	Operation	Current Letter	Node Children Keys	Pointer Changes	Visual State
1	Start at root	-	['c', 'b']	current = root	root -> {c, b}
2	Check letter 'c'	c	['a']	current = node 'c'	root -> c -> {a}, b -> {...}
3	Check letter 'a'	a	['t']	current = node 'a'	root -> c -> a -> {t}, b -> {...}
4	Check letter 't'	t		current = node 't'	root -> c -> a -> t (endOfWord=true), b -> {...}
5	End of word reached	-	-	-	Word found: 'cat'
6	Start at root	-	['c', 'b']	current = root	root -> {c, b}
7	Check letter 'b'	b	['a']	current = node 'b'	root -> c -> {...}, b -> a -> {...}
8	Check letter 'a'	a	['d']	current = node 'a'	root -> c -> {...}, b -> a -> d -> {...}
9	Check letter 'd'	d		current = node 'd'	root -> c -> {...}, b -> a -> d (endOfWord=true)
10	End of word reached	-	-	-	Word found: 'bad'
11	Start at root	-	['c', 'b']	current = root	root -> {c, b}
12	Check letter 'c'	c	['a']	current = node 'c'	root -> c -> {a}, b -> {...}
13	Check letter 'o'	o		Letter not found	Word NOT found: 'cow'

💡 Search stops when a letter is not found or all letters are matched and endOfWord is true.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 7	After Step 8	After Step 9	After Step 10	After Step 12	After Step 13
current	root	node 'c'	node 'a'	node 't'	node 't'	node 'b'	node 'a'	node 'd'	node 'd'	node 'c'	node 'c'
currentLetter	-	c	a	t	-	b	a	d	-	c	o
wordFound	false	false	false	false	true	false	false	false	true	false	false

Key Moments - 3 Insights

Why does the search stop immediately when a letter is not found in children?

Because if the current letter is missing in the children nodes (see step 13 in execution_table), the word cannot be formed from the trie, so the search ends early.

Why do we check if the current node is endOfWord after the last letter?

Because a word might be a prefix of another word. Only if endOfWord is true (step 5 and 10) do we confirm the full word exists.

What happens if the word is empty?

The search would start and end at the root. Since no letters are checked, the result depends on whether root marks endOfWord, usually false.

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'current' node after step 4?

A node 't'

B root

C node 'a'

D node 'c'

💡 Hint

Check the 'Pointer Changes' and 'Current Letter' columns at step 4.

At which step does the search fail because the letter is not found?

A Step 10

B Step 13

C Step 5

D Step 9

💡 Hint

Look for the row where 'Letter not found' is mentioned in 'Pointer Changes'.

If the word was 'bat' instead of 'bad', which step would change in the execution_table?

A Step 13 would be successful

B Step 4 would have children keys ['t']

C Step 9 would have children keys ['t'] instead of []

D Step 2 would change to letter 'b'

💡 Hint

Consider the children keys of the node for the last letter in the word.

Concept Snapshot

Word Search in Trie:
- Start at root node
- For each letter in word, check if child node exists
- Move pointer to child if found
- If letter missing, word not found
- After last letter, check if node marks end of word
- Return true if endOfWord is true, else false

Full Transcript

This visualization shows how to search a word in a trie data structure. We start at the root node and check each letter of the word one by one. If the letter exists as a child node, we move to that node and continue. If any letter is missing, the search stops and the word is not found. After checking all letters, if the last node marks the end of a word, the search returns true, confirming the word exists in the trie. The execution table traces the pointer movements and node children at each step for words like 'cat', 'bad', and a failed search for 'cow'. Key moments clarify why the search stops early and why endOfWord matters. The quiz tests understanding of pointer positions and failure steps.

Practice

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

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To store words in a linked list format

D. To perform arithmetic operations on words

Solution

1. Step 1: Understand the Trie structure

   A Trie stores characters in a tree where each path represents a prefix of words.

2. Step 2: Identify the use in word search

   This structure allows quick prefix-based search, making it efficient for word search problems.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is all about prefixes and fast word lookup [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie stores words linearly
• Assuming Trie performs arithmetic

2. Which of the following is the correct TypeScript syntax to declare a Trie node class with a children map and an end-of-word boolean?

easy

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

B. class TrieNode { children: string[]; isEndOfWord: number; constructor() { this.children = []; this.isEndOfWord = 0; } }

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

D. class TrieNode { children: object; isEndOfWord: string; constructor() { this.children = {}; this.isEndOfWord = 'false'; } }

Solution

1. Step 1: Check children type

   Children should be a Map from string to TrieNode for efficient character mapping.

2. Step 2: Check isEndOfWord type and initialization

   It should be a boolean initialized to false to mark word endings correctly.

3. Final Answer:

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

4. Quick Check:

   Correct types and initialization [OK]

Hint: Use Map and boolean for end flag [OK]

Common Mistakes:

• Using array instead of Map for children
• Using wrong types for isEndOfWord
• Initializing isEndOfWord incorrectly

3. Given the following TypeScript code snippet for searching a word in a Trie, what will be the output when searching for the word "cat" if only "car" and "cap" are inserted?

class TrieNode {
  children = new Map();
  isEndOfWord = false;
}

class Trie {
  root = new TrieNode();

  insert(word: string) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
    }
    node.isEndOfWord = true;
  }

  search(word: string): boolean {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch)!;
    }
    return node.isEndOfWord;
  }
}

const trie = new Trie();
trie.insert("car");
trie.insert("cap");
console.log(trie.search("cat"));

medium

A. true

B. false

C. undefined

D. Runtime error

Solution

1. Step 1: Trace insertion of "car" and "cap"

   Both words create nodes for 'c', 'a', then diverge at 'r' and 'p' respectively, marking those ends as true.

2. Step 2: Trace search for "cat"

   Search finds 'c' and 'a', but 't' is not a child of 'a', so search returns false.

3. Final Answer:

   false -> Option B

4. Quick Check:

   Word not inserted = false [OK]

Hint: If last char missing, search returns false [OK]

Common Mistakes:

• Assuming partial prefix means true
• Confusing isEndOfWord with node existence
• Expecting undefined instead of false

4. Identify the bug in the following TypeScript Trie search method that causes it to always return false:

search(word: string): boolean {
  let node = this.root;
  for (const ch of word) {
    if (!node.children.has(ch)) return false;
    node = node.children.get(ch)!;
  }
  return node.isEndOfWord === false;
}

medium

A. The method should return true before the loop ends

B. The loop should iterate backwards over the word

C. The children map should be an array instead

D. The return condition should be node.isEndOfWord, not its negation

Solution

1. Step 1: Analyze the return statement

   The method returns node.isEndOfWord === false, which means it returns true if the word is NOT ending here.

2. Step 2: Correct the return logic

   It should return node.isEndOfWord to confirm the word ends at this node.

3. Final Answer:

   The return condition should be node.isEndOfWord, not its negation -> Option D

4. Quick Check:

   Return true if word ends here [OK]

Hint: Return node.isEndOfWord directly to confirm word end [OK]

Common Mistakes:

• Returning negation of isEndOfWord
• Changing loop direction unnecessarily
• Using wrong data structure for children

5. You want to implement a function that finds all words in a Trie starting with a given prefix. Which approach correctly combines Trie traversal and backtracking to collect all matching words?

hard

A. Search each word in the Trie individually to check prefix match

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

C. Traverse Trie nodes for prefix, then recursively collect words from that node using backtracking

D. Use a hash map to map prefixes to words without Trie traversal

Solution

1. Step 1: Traverse Trie to prefix node

   Follow characters of prefix to reach the node representing last prefix character.

2. Step 2: Use backtracking from prefix node

   Recursively explore all children nodes to collect complete words starting with prefix.

3. Final Answer:

   Traverse Trie nodes for prefix, then recursively collect words from that node using backtracking -> Option C

4. Quick Check:

   Prefix traversal + backtracking = Traverse Trie nodes for prefix, then recursively collect words from that node using backtracking [OK]

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

Common Mistakes:

• Checking all words instead of prefix traversal
• Filtering array instead of Trie traversal
• Using hash map without Trie structure