Trie Search Operation in DSA Javascript - Execution Trace

Concept Flow - Trie Search Operation

Start at root node

↓

For each character in word

↓

Check if character exists as child

↓

Move to child

↓

Repeat for next character

↓

After last character

↓

Check if current node marks word end

↓

Word found

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 and the last node marks the end of a word, the word exists.

Execution Sample

DSA Javascript

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

This code checks each character of the word in the trie. If any character is missing, it returns false. If all characters are found and the last node marks the end of a word, it returns true.

Execution Table

Step	Operation	Current Character	Node Children Keys	Pointer Change	Visual State
1	Start search	-	c, b	node = root	root → {c, b}
2	Check character	c	a	node = node.children['c']	root → c → {a}
3	Check character	a	r, t	node = node.children['a']	root → c → a → {r, t}
4	Check character	t		node = node.children['t']	root → c → a → t (isEnd: true)
5	Check end of word	-	-	-	Word found: 'cat' exists
6	Start search	-	c, b	node = root	root → {c, b}
7	Check character	c	a	node = node.children['c']	root → c → {a}
8	Check character	a	r, t	node = node.children['a']	root → c → a → {r, t}
9	Check character	r		node = node.children['r']	root → c → a → r (isEnd: true)
10	Check end of word	-	-	-	Word found: 'car' exists
11	Start search	-	c, b	node = root	root → {c, b}
12	Check character	c	a	node = node.children['c']	root → c → {a}
13	Check character	o		No child 'o', stop	Word not found: 'co' missing
14	End search	-	-	-	Word 'co' does not exist

💡 Search stops when a character is missing or after confirming the last node marks word end.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	After Step 7	After Step 8	After Step 9	After Step 11	After Step 12	After Step 13	Final
node	root	node.children['c']	node.children['a']	node.children['t']	root	node.children['c']	node.children['a']	node.children['r']	root	node.children['c']	null	null
current character	-	c	a	t	-	c	a	r	-	c	o	-

Key Moments - 3 Insights

Why does the search stop immediately when a character is missing in the children?

Because if the current node does not have the next character as a child (see Step 13), the word cannot be formed in the trie, so the search ends early.

Why do we check if the last node has isEnd true after traversing all characters?

Because the trie may have nodes for prefixes of words. Only if isEnd is true (Step 5 and 10) does the node represent a complete stored word.

What happens if we search for a prefix that is not a complete word?

The search will find all characters but fail at the isEnd check (Step 14), returning false since the prefix is not marked as a full word.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the current node's children keys?

A ["t"]

B []

C ["a"]

D ["r"]

💡 Hint

Check the 'Node Children Keys' column at Step 4 in the execution_table.

At which step does the search stop because the character is missing?

A Step 14

B Step 9

C Step 13

D Step 5

💡 Hint

Look for the step where 'No child' is mentioned in the 'Pointer Change' column.

If the word 'car' was not marked with isEnd true, what would be the search result at Step 10?

A Word not found

B Search continues

C Word found

D Error

💡 Hint

Refer to the 'Check end of word' operation and the importance of isEnd flag in the execution_table.

Concept Snapshot

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

Full Transcript

The trie search operation begins at the root node. For each character in the word, it checks if the character exists as a child of the current node. If it does, the pointer moves to that child node. If any character is missing, the search stops immediately and returns false. After all characters are found, the search checks if the current node marks the end of a word using the isEnd flag. If true, the word exists in the trie; otherwise, it does not. This process ensures efficient prefix-based search in the trie data structure.