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.