Word Search in Trie in DSA Javascript - Execution Trace

Concept Flow - Word Search in Trie

Start at root node

↓

For each letter in word

↓

Check if letter child exists?

No→Word NOT found

Yes↓

Move to child node

↓

Repeat for next letter

↓

After last letter, check isEnd?

No→Word NOT found

Yes↓

Word FOUND in Trie

Start from root, check each letter's child node exists, move down nodes, finally check if last node marks word end.

Execution Sample

DSA Javascript

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

function searchWord(root, word) {
  let node = root;
  for (const char of word) {
    if (!node.children[char]) return false;
    node = node.children[char];
  }
  return node.isEnd;
}

Searches a word in a Trie by traversing nodes for each letter and checking end marker.

Execution Table

Step	Operation	Current Node Letter	Child Exists?	Move To Node	Visual State
1	Start at root	root	N/A	root	root (children: a, b)
2	Check letter 'b'	root	Yes	node for 'b'	root -> b
3	Check letter 'a'	b	Yes	node for 'a'	root -> b -> a
4	Check letter 'd'	a	Yes	node for 'd'	root -> b -> a -> d
5	End of word reached	d	N/A	N/A	node 'd' isEnd = true
6	Return result	d	N/A	N/A	Word FOUND
7	Start at root	root	N/A	root	root (children: a, b)
8	Check letter 'b'	root	Yes	node for 'b'	root -> b
9	Check letter 'a'	b	Yes	node for 'a'	root -> b -> a
10	Check letter 't'	a	No	N/A	No child 't' under 'a'
11	Return result	a	N/A	N/A	Word NOT found

💡 Search ends when all letters checked and isEnd true (word found) or missing child (word not found)

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
node	root	node for 'b'	node for 'a'	node for 'd'	node for 'd'	node for 'd'
letter	N/A	'b'	'a'	'd'	N/A	N/A
isEnd	N/A	N/A	N/A	true	true	true

Key Moments - 3 Insights

Why do we check if the child node exists before moving?

Because if the child node for a letter does not exist (see Step 10), the word cannot be in the Trie, so we stop searching.

Why do we check isEnd only after the last letter?

Because isEnd marks if a complete word ends at that node. Without it, the prefix might exist but not the full word (see Step 5).

What happens if the word is empty?

The search starts and ends at root. If root.isEnd is true, empty word is found; else not. This is a special case not shown here.

Visual Quiz - 3 Questions

Look at the execution table, what is the current node letter at Step 4?

A 'b'

B 'a'

C 'd'

D 'root'

💡 Hint

Check the 'Current Node Letter' column at Step 4 in the execution_table.

At which step does the search find that a child node does NOT exist?

A Step 9

B Step 11

C Step 10

D Step 8

💡 Hint

Look for 'Child Exists?' column with 'No' in the execution_table.

If the word searched was 'bad', what would be the value of isEnd at the final node?

A true

B false

C undefined

D null

💡 Hint

Refer to variable_tracker row for 'isEnd' after Step 5.

Concept Snapshot

Word Search in Trie:
- Start at root node
- For each letter, check if child node exists
- Move to child node if exists
- After last letter, check isEnd flag
- Return true if isEnd 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. For each letter, we look if the current node has a child node matching that letter. If yes, we move to that child node and continue. If at any point the child node does not exist, the word is not in the Trie. After checking all letters, we verify if the last node marks the end of a word using the isEnd flag. If it does, the word is found; otherwise, it is not. The execution table traces these steps with the current node, child existence, and visual state of the Trie. The variable tracker shows how the node pointer and isEnd flag change during the search. Key moments clarify why we check child nodes and the isEnd flag. The quiz tests understanding of node letters, missing children, and end flags.