Trie Search Operation in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the current character exists in the children nodes.

DSA Python

if char [1] node.children:

Drag options to blanks, or click blank then click option'

Ain

Bnot in

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' instead of 'in' to check dictionary keys.

Using 'not in' which checks for absence, not presence.

We use in to check if the character is a key in the children dictionary.

2fill in blank

medium

Complete the code to move to the next node for the current character.

DSA Python

node = node.[1][char]

Drag options to blanks, or click blank then click option'

Akeys

Bchildren

Cvalues

Ditems

Attempts:

3 left

💡 Hint

Common Mistakes

Using keys or values which return views, not dictionaries.

Using items which returns key-value pairs, not a dictionary.

The children dictionary holds the next nodes for each character.

3fill in blank

hard

Fix the error in the return statement to correctly indicate if the word exists in the trie.

DSA Python

return node.[1]

Drag options to blanks, or click blank then click option'

Ais_word

Bword_end

Cis_end_of_word

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect attribute names that do not exist in the node.

Confusing the attribute with the word itself.

The attribute is_end_of_word is commonly used to mark the end of a valid word in a trie node.

4fill in blank

hard

Fill both blanks to complete the loop that iterates over each character in the word and checks the trie.

DSA Python

for [1] in [2]:
    if char not in node.children:
        return False
    node = node.children[char]

Drag options to blanks, or click blank then click option'

Achar

Bword

Cnode

Dstring

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect variable names that don't represent characters or the word.

Using node or string which are not the iterable or loop variable here.

The loop variable should be char to represent each character, and the iterable is the word string.

5fill in blank

hard

Fill all three blanks to complete the search function that returns True if the word is found in the trie.

DSA Python

def search(root, word):
    node = root
    for [1] in [2]:
        if [3] not in node.children:
            return False
        node = node.children[char]
    return node.is_end_of_word

Drag options to blanks, or click blank then click option'

Achar

Bword

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names inconsistently.

Checking for node instead of char in children.

The loop variable is char, the iterable is word, and the character checked in children is char.

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