Trie Search Operation in DSA Python - 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 down the tree represent words.

beginner

How does the search operation work in a Trie?

Search starts from the root and follows nodes matching each character of the 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 at some character?

It means the word is not present in the Trie because the path for that character does not exist from the current node.

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

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

The time complexity is O(m), where m is the length of the word being searched, since each character is checked once.

In a Trie search, what does reaching a node that marks the end of a word indicate?

A The search should restart

B The word does not exist

C The word exists in the Trie

D The word is a prefix only

If the last node of the search path marks the end of a word, it means the full word exists in the Trie.

What happens if a character in the search word is not found in the current Trie node's children?

A The search restarts from root

B The search fails; word not found

C The search continues ignoring that character

D The word is partially matched

If a character is missing in the children nodes, the word cannot be found in the Trie.

What is the starting point for a Trie search operation?

A Leaf node

B Middle node

C Random node

D Root node

Trie search always starts from the root node.

Which of these best describes the Trie search time complexity?

A Depends on the length of the word searched

B Depends on the number of nodes in the Trie

C Always constant time

D Depends on the number of words stored

Search time depends on the length of the word, as each character is checked once.

Why is Trie search useful for autocomplete features?

A Because it quickly finds all words with a given prefix

B Because it stores words in alphabetical order

C Because it uses less memory than other structures

D Because it sorts words by length

Trie allows fast prefix searches, which is essential for autocomplete.

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

Think about moving from one character node to the next.

What are the conditions that determine if a word is found or not found during a Trie search?

Consider both path existence and end of word marking.

Practice

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

easy

A. If a given word exists completely in the Trie

B. If a given prefix exists in the Trie

C. If the Trie is empty

D. If the Trie contains duplicate words

Solution

1. Step 1: Understand the purpose of search in Trie

   The search operation checks if the exact word is stored in the Trie, not just a prefix.

2. Step 2: Differentiate between search and prefix check

   While prefix check looks for any starting sequence, search requires the full word to be present and marked as an end of word.

3. Final Answer:

   If a given word exists completely in the Trie -> Option A

4. Quick Check:

   Search = full word check [OK]

Hint: Search checks full word presence, not just prefix [OK]

Common Mistakes:

• Confusing search with prefix check
• Thinking search returns true for partial matches
• Assuming search checks for duplicates

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

easy

A. if char in current_node.children:

B. if current_node.children.contains(char):

C. if current_node.children.has_key(char):

D. if char.exists_in(current_node.children):

Solution

1. Step 1: Recall Python dictionary membership syntax

   Trie children are usually stored in a dictionary. To check if a key exists, use key in dict.

2. Step 2: Evaluate each option

   if char in current_node.children: uses correct Python syntax. Options A, B, and C use invalid or non-existent methods in Python dictionaries.

3. Final Answer:

   if char in current_node.children: -> Option A

4. Quick Check:

   Use 'in' keyword for dict keys [OK]

Hint: Use 'in' keyword to check dictionary keys in Python [OK]

Common Mistakes:

• Using non-existent dictionary methods
• Confusing syntax with other languages
• Trying to call methods on dict keys

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

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

trie = Trie()
trie.insert('cat')
print(trie.search('cat'))
print(trie.search('ca'))
print(trie.search('bat'))

medium

A. False\nFalse\nFalse

B. True\nTrue\nFalse

C. True\nFalse\nTrue

D. True\nFalse\nFalse

Solution

1. Step 1: Insert 'cat' into the Trie

   The word 'cat' is inserted, marking the last node's is_end as True.

2. Step 2: Search for 'cat', 'ca', and 'bat'

   'cat' exists fully with is_end True, so returns True. 'ca' is prefix but not a full word, so returns False. 'bat' is not inserted, so returns False.

3. Final Answer:

   True False False -> Option D

4. Quick Check:

   Full word present = True, prefix only = False [OK]

Hint: Search returns True only if full word and is_end True [OK]

Common Mistakes:

• Assuming prefix search returns True
• Not setting is_end flag on insert
• Confusing missing words with prefixes

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

def search(self, word):
    node = self.root
    for char in word:
        if char in node.children:
            node = node.children[char]
        else:
            return False
    return True

medium

A. Change 'if char in node.children' to 'if char not in node.children'

B. Return node.is_end instead of True at the end

C. Initialize node as None before loop

D. Add a break statement inside the loop

Solution

1. Step 1: Analyze the return statement

   The method returns True after traversing all characters, but it should confirm the word ends here by checking is_end flag.

2. Step 2: Correct the return value

   Return node.is_end to ensure the word is complete in the Trie, not just a prefix.

3. Final Answer:

   Return node.is_end instead of True at the end -> Option B

4. Quick Check:

   Check is_end flag to confirm full word [OK]

Hint: Always check is_end flag after traversal [OK]

Common Mistakes:

• Returning True without checking is_end
• Incorrect if condition reversing
• Unnecessary break statements

5. You want to implement a search in a Trie that returns True if the word exists or if any word in the Trie starts with the given prefix. Which modification to the standard search method achieves this?

hard

A. Return node.is_end only after traversal

B. Return False if any character is missing during traversal

C. Return True after traversing all characters without checking is_end

D. Return True only if the prefix length equals the word length

Solution

1. Step 1: Understand the difference between full word and prefix search

   Full word search requires is_end True; prefix search only requires traversal success.

2. Step 2: Modify return to support prefix search

   Return True after successfully traversing all characters without checking is_end to allow prefix matches.

3. Final Answer:

   Return True after traversing all characters without checking is_end -> Option C

4. Quick Check:

   Prefix search = True if traversal succeeds [OK]

Hint: For prefix search, ignore is_end flag, return True if path exists [OK]

Common Mistakes:

• Checking is_end for prefix search
• Returning False prematurely
• Confusing prefix length with word length