Trie Search Operation in DSA Go - Execution Trace

Concept Flow - Trie Search Operation

Start at root node

↓

Check next character in word

↓

Does child node for char exist?

No→Word NOT found, stop

Yes↓

Move pointer to child node

↓

More characters left?

Yes→Repeat check for next char

No↓

Is current node marked as end of word?

Yes→Word FOUND

No↓

Word NOT found

The search starts at the root and checks each character of the word by moving through child nodes. If any character node is missing, search stops. If all characters are found and the last node marks end of word, the word exists.

Execution Sample

DSA Go

func Search(root *TrieNode, word string) bool {
    current := root
    for _, ch := range word {
        if current.children[ch-'a'] == nil {
            return false
        }
        current = current.children[ch-'a']
    }
    return current.isEnd
}

Searches for a word in the trie by traversing nodes for each character.

Execution Table

Step	Operation	Current Character	Node Exists?	Pointer Change	Trie State Visual
1	Start at root	-	N/A	current = root	root →
2	Check character 'c'	c	Yes	current = child node for 'c'	root → c
3	Check character 'a'	a	Yes	current = child node for 'a'	root → c → a
4	Check character 't'	t	Yes	current = child node for 't'	root → c → a → t
5	No more characters	-	-	-	At node 't' (isEnd = true)
6	Check isEnd flag	-	N/A	-	Word FOUND
7	End search	-	-	-	Search complete

💡 Search stops because all characters found and last node marks end of word.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	root	node for 'c'	node for 'a'	node for 't'	node for 't'	node for 't'
current Character	-	'c'	'a'	't'	-	-

Key Moments - 3 Insights

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

Because if the child node does not exist (see Step 2-4 in execution_table), it means the word cannot be formed from the trie, so we stop searching immediately.

Why do we check the isEnd flag after traversing all characters?

Because even if all characters are found (Step 5), the word is only valid if the last node marks the end of a word (Step 6). Otherwise, the searched string is just a prefix, not a complete word.

What happens if the word is empty?

The search starts and ends at the root node. If root.isEnd is true, empty word exists; otherwise, it does not. This is a special edge case.

Visual Quiz - 3 Questions

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

A Node for 'c'

B Node for 't'

C Node for 'a'

D Root node

💡 Hint

Check the 'Pointer Change' and 'Current Character' columns at Step 3 in execution_table.

At which step does the search confirm the word is found?

A Step 6

B Step 5

C Step 4

D Step 7

💡 Hint

Look for the step where 'Word FOUND' appears in the 'Trie State Visual' column.

If the child node for 'a' was missing at Step 3, what would happen?

A Search continues to next character

B Search stops and returns false

C Search marks word as found

D Search restarts from root

💡 Hint

Refer to the 'Node Exists?' column and the concept_flow where missing child node leads to stopping search.

Concept Snapshot

Trie Search Operation:
- Start at root node
- For each character in word:
  - Check if child node exists
  - Move to child node if yes
  - Stop and return false if no
- After last char, check isEnd flag
- Return true if isEnd is true, else false

Full Transcript

The trie search operation begins at the root node. For each character in the word, it checks if a child node exists for that character. If it does, the search pointer moves to that child node. If not, the search stops and returns false, meaning the word is not in the trie. After all characters are checked, the search verifies if the current node marks the end of a word. If yes, the word is found; otherwise, it is 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 check for?

easy

A. The number of words stored in the Trie

B. If the Trie is empty

C. If a given word exists in the Trie

D. The length of the longest word 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 stored in the Trie.

2. Step 2: Differentiate from other Trie operations

   Other operations like counting words or checking emptiness are not the purpose of search.

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 if the exact word is stored [OK]

Common Mistakes:

• Confusing search with counting words
• Thinking search checks Trie emptiness
• Assuming search returns word length

2. Which of the following is the correct way to check if a character node exists in a Trie map in Go?

easy

A. if node.children[char] != nil

B. if node.children[char] == nil

C. if node.children.contains(char)

D. if node.children.has(char)

Solution

1. Step 1: Recall Go map access syntax

   In Go, to check if a key exists in a map, you check if the value is not nil (for pointer or map values).

2. Step 2: Apply to Trie children map

   Trie children are stored in a map from rune to *TrieNode, so checking if node.children[char] != nil confirms existence.

3. Final Answer:

   if node.children[char] != nil -> Option A

4. Quick Check:

   Go map key exists check [OK]

Hint: Check map key by comparing to nil in Go [OK]

Common Mistakes:

• Using contains or has methods (not in Go maps)
• Checking for equality to nil incorrectly
• Confusing map key existence with value presence

3. Consider the following Go code snippet for searching a word in a Trie:

func (t *Trie) Search(word string) bool {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return node.isEnd
}

What will be the output of Search("cat") if the Trie contains the words "car", "cat", and "cap"?

medium

A. compilation error

B. true

C. runtime error

D. false

Solution

1. Step 1: Trace the search for "cat" in the Trie

   The loop checks each character 'c', 'a', 't' in order. Since "cat" is inserted, all nodes exist and node.isEnd is true at 't'.

2. Step 2: Return value after traversal

   Because node.isEnd is true at the last character, the function returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Word "cat" exists in Trie = true [OK]

Hint: Search returns true if last node marks word end [OK]

Common Mistakes:

• Ignoring isEnd flag and returning true always
• Assuming false if any child exists
• Confusing runtime errors with nil checks

4. The following Go code for Trie search has a bug. What is the error?

func (t *Trie) Search(word string) bool {
    node := t.root
    for i := 0; i <= len(word); i++ {
        ch := rune(word[i])
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return node.isEnd
}

medium

A. Missing check for empty Trie root

B. Incorrect rune conversion for characters

C. Returning wrong boolean value

D. Index out of range error due to loop condition

Solution

1. Step 1: Analyze the loop condition

   The loop runs from i = 0 to i <= len(word), which means it tries to access word[len(word)] causing index out of range error.

2. Step 2: Correct loop boundary

   The loop should run with i < len(word) to avoid accessing beyond the string length.

3. Final Answer:

   Index out of range error due to loop condition -> Option D

4. Quick Check:

   Loop boundary error causes runtime panic [OK]

Hint: Use i < len(word), not i <= len(word) in loops [OK]

Common Mistakes:

• Using <= instead of < in loop
• Ignoring string length limits
• Assuming rune conversion causes error

5. You want to modify the Trie search function to support prefix search (check if any word starts with the given prefix). Which change is correct?

hard

A. Return true immediately after traversing all prefix characters without checking isEnd

B. Return true only if isEnd is true at last prefix character

C. Return false if any character node is missing, else return false always

D. Return true only if prefix length equals word length stored

Solution

1. Step 1: Understand prefix search goal

   Prefix search should return true if the prefix exists as a path in the Trie, regardless of isEnd flag.

2. Step 2: Modify search to return true after prefix traversal

   After checking all prefix characters exist, return true immediately without checking isEnd.

3. Final Answer:

   Return true immediately after traversing all prefix characters without checking isEnd -> Option A

4. Quick Check:

   Prefix search ignores isEnd, returns true if path exists [OK]

Hint: For prefix, return true after full prefix traversal [OK]

Common Mistakes:

• Checking isEnd for prefix search
• Returning false even if prefix path exists
• Confusing prefix length with word length