Trie Search Operation in DSA Typescript - Execution Trace

Concept Flow - Trie Search Operation

Start at root node

↓

For each character in word

↓

Check if character exists in current node's children

↓

Move to child node

↓

After last character, check isEndOfWord

↓

Word found

↓

End

The search starts at the root and checks each character in the word. If a character is missing, search stops. If all characters are found, it checks if the last node marks the end of a word.

Execution Sample

DSA Typescript

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

This code searches for a word in the trie by traversing nodes for each character and returns true if the word exists.

Execution Table

Step	Operation	Current Character	Node Children Keys	Pointer Change	Visual State
1	Start at root	-	a, b, c	node = root	root → {a, b, c}
2	Check 'c'	c	a, b, c	node = node.children.get('c')	root → c node → {a, t}
3	Check 'a'	a	a, t	node = node.children.get('a')	c node → a node → {t}
4	Check 't'	t	t	node = node.children.get('t')	a node → t node → {}
5	Check isEndOfWord	-	-	-	t node isEndOfWord = true
6	Return result	-	-	-	Word found: true

💡 Search ends after checking all characters and confirming isEndOfWord is true

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
node	root	c node	a node	t node	t node

Key Moments - 3 Insights

Why do we check isEndOfWord after traversing all characters?

Because a node can exist for a prefix but not mark a complete word. Checking isEndOfWord confirms the word ends here (see Step 5 in execution_table).

What happens if a character is missing in children?

The search stops immediately and returns false, as shown in Step 2 where if 'c' was missing, we would return false.

Why do we update 'node' pointer at each character?

To move deeper into the trie along the path of the word. Each update points to the next node representing the next character (see Pointer Change column).

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'node' variable after Step 3?

A a node

B c node

C root node

D t node

💡 Hint

Check the 'Pointer Change' and 'Variable Tracker' after Step 3

At which step does the search confirm the word exists?

A Step 4

B Step 5

C Step 2

D Step 6

💡 Hint

Look at the 'Operation' and 'Visual State' columns for isEndOfWord check

If the character 'a' was missing in Step 3, what would happen?

A Search continues to next character

B Return true immediately

C Return false immediately

D Skip character and continue

💡 Hint

Refer to the 'Operation' and 'Pointer Change' logic in Step 2 for missing character

Concept Snapshot

Trie Search Operation:
- Start at root node
- For each character, move to child node if exists
- If missing, return false
- After last char, check isEndOfWord
- Return true if word ends here, else false

Full Transcript

The Trie Search Operation starts at the root node. For each character in the word, it checks if the character exists among the current node's children. If it does, the pointer moves to that child node. If any character is missing, the search stops and returns false. After all characters are found, the search checks if the current node marks the end of a word (isEndOfWord). If yes, the word exists in the trie and returns true; otherwise, it returns false.