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.

Practice

1. What does the search operation in a Trie data structure primarily check for?

easy

A. The length of the longest word in the Trie

B. If the Trie is empty

C. If a given word exists in the Trie

D. The number of words stored in the Trie

Solution

1. Step 1: Understand the purpose of Trie search

   The search operation in a Trie is designed to check if a specific word is present in the Trie by traversing nodes corresponding to each character.

2. Step 2: Identify what the search confirms

   It confirms the presence or absence of the entire word, not the count or length of words stored.

3. Final Answer:

   If a given word exists in the Trie -> Option C

4. Quick Check:

   Trie search checks word existence [OK]

Hint: Search checks full word presence in Trie nodes [OK]

Common Mistakes:

• Confusing search with counting words
• Thinking search returns word length
• Assuming search checks if Trie is empty

2. Which of the following is the correct way to check if a character node exists in a Trie during search in JavaScript?

easy

A. if (node.char !== null)

B. if (node[char] !== undefined)

C. if (node.has(char))

D. if (node.char === true)

Solution

1. Step 1: Understand Trie node structure in JavaScript

   Trie nodes are usually objects where keys are characters. Checking if a character exists uses property access and undefined check.

2. Step 2: Identify correct syntax for existence check

   Using node[char] !== undefined correctly checks if the character key exists in the node object.

3. Final Answer:

   if (node[char] !== undefined) -> Option B

4. Quick Check:

   Check node property with !== undefined [OK]

Hint: Use node[char] !== undefined to check character node [OK]

Common Mistakes:

• Using dot notation with variable char
• Using incorrect method like has() on object
• Checking for null instead of undefined

3. What will be the output of the following JavaScript code snippet?

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

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEnd = true;
  }

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

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

medium

A. true false

B. false true

C. true true

D. false false

Solution

1. Step 1: Insert words 'cat' and 'car' into Trie

   Both words are inserted by creating nodes for each character and marking the last node's isEnd as true.

2. Step 2: Search for 'cat' and 'cap'

   'cat' exists fully with isEnd true, so search returns true. 'cap' is missing 'p' node, so search returns false.

3. Final Answer:

   true false -> Option A

4. Quick Check:

   Search 'cat' = true, 'cap' = false [OK]

Hint: Search returns true only if full word and isEnd true [OK]

Common Mistakes:

• Assuming partial matches return true
• Not setting isEnd flag on insert
• Confusing children object access

4. Identify the bug in the following Trie search method and select the correct fix:

search(word) {
  let node = this.root;
  for (const char of word) {
    if (node.children[char] === undefined) return false;
    node = node.children[char];
  }
  return true;
}

medium

A. Use 'for (let i=0; i

B. Change '===' to '!==' in the if condition

C. Initialize node with a new TrieNode inside the method

D. Return node.isEnd instead of true at the end

Solution

1. Step 1: Analyze the search method's return value

   The method returns true after traversing all characters without checking if the last node marks the end of a word.

2. Step 2: Correct the return to check word completion

   Return node.isEnd to confirm the word ends here, not just prefix exists.

3. Final Answer:

   Return node.isEnd instead of true at the end -> Option D

4. Quick Check:

   Check isEnd flag to confirm full word [OK]

Hint: Always check isEnd flag after traversal [OK]

Common Mistakes:

• Returning true without isEnd check
• Changing comparison operator incorrectly
• Unnecessary loop syntax changes

5. Given a Trie containing the words ['apple', 'app', 'bat', 'bath'], which of the following search queries will return true? Assume the search method correctly checks for full word presence. Select the correct combination.

hard

A. search('app'), search('bat'), search('bath')

B. search('appl'), search('bat'), search('bath')

C. search('apple'), search('bat'), search('batman')

D. search('app'), search('bath'), search('batman')

Solution

1. Step 1: Identify words present in the Trie

   The Trie contains 'apple', 'app', 'bat', and 'bath'. Only these exact words return true on search.

2. Step 2: Check each option's search queries

   search('app'), search('bat'), search('bath') searches 'app', 'bat', 'bath' all present. Others include partial or missing words like 'appl' or 'batman' which return false.

3. Final Answer:

   search('app'), search('bat'), search('bath') -> Option A

4. Quick Check:

   Only full words in Trie return true [OK]

Hint: Search true only for full words inserted in Trie [OK]

Common Mistakes:

• Assuming partial words return true
• Confusing prefixes with full words
• Including words not inserted in Trie