Trie Search Operation in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths from root to leaves represent words.

beginner

How does the search operation work in a Trie?

Search starts at the root and follows nodes matching each character of the search word. If all characters are found and the last node marks the end of a word, the search is successful.

beginner

What does it mean if a search in a Trie fails before reaching the end of the word?

It means the word or prefix does not exist in the Trie because a required character node is missing along the path.

intermediate

Why is Trie search efficient for prefix matching?

Because Trie nodes represent characters in sequence, searching for prefixes only requires traversing nodes for those characters, making prefix queries fast and simple.

intermediate

In Go, what is a common way to represent children nodes in a Trie?

Children nodes are often represented as a map from rune (character) to *TrieNode, allowing quick lookup of child nodes by character.

In a Trie search, what happens if a character node is missing during traversal?

A The search continues to the next character

B The search fails; the word is not in the Trie

C The Trie automatically adds the missing node

D The search returns the closest matching word

If a character node is missing, it means the word does not exist in the Trie.

What does the end-of-word marker in a Trie node signify?

A That a complete word ends at this node

B That the node is a leaf node

C That the node has no children

D That the node is the root

The end-of-word marker shows that the path from root to this node forms a complete stored word.

Which data structure is commonly used to store children nodes in a Go Trie implementation?

A Slice of integers

B Array of booleans

C Linked list of strings

D Map from rune to *TrieNode

A map from rune to *TrieNode allows quick lookup of child nodes by character.

What is the time complexity of searching a word of length n in a Trie?

A O(n^2)

B O(log n)

C O(n)

D O(1)

Search time depends linearly on the length of the word, O(n).

Why is Trie search preferred over hash maps for prefix queries?

A Tries allow efficient prefix search without hashing

B Tries use less memory

C Hash maps are slower for exact matches

D Tries do not require keys

Tries store characters in sequence, making prefix search straightforward and efficient.

Explain step-by-step how a search operation works in a Trie for the word "cat".

Think about following each character node in order.

Describe how missing nodes affect the search operation in a Trie.

Consider what happens when you cannot find the next letter.

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