Word Search in Trie in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Searching Words in Trie

What is the output of the following code that inserts words into a Trie and searches for some words?

DSA Python

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()
words_to_insert = ["cat", "car", "cart", "dog"]
for w in words_to_insert:
    trie.insert(w)

search_words = ["car", "cart", "cap", "dog", "do"]
results = {w: trie.search(w) for w in search_words}
print(results)

A {"car": true, "cart": true, "cap": true, "dog": true, "do": false}

B {"car": true, "cart": true, "cap": false, "dog": true, "do": false}

C {"car": true, "cart": false, "cap": false, "dog": true, "do": false}

D {"car": true, "cart": true, "cap": false, "dog": false, "do": false}

💡 Hint

Remember that search returns True only if the whole word is inserted and marked as end.

The words 'car', 'cart', and 'dog' were inserted fully, so search returns True for them. 'cap' and 'do' were not inserted as complete words, so search returns False.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the role of the 'is_end' flag in a Trie node?

A It marks the node as the end of a valid word stored in the Trie.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It points to the parent node in the Trie.

💡 Hint

Think about how the Trie knows when a word finishes.

The 'is_end' flag is True only at nodes where a complete word ends, distinguishing prefixes from full words.

🔧 Debug

advanced

Identify the Error in Trie Search Method

What error will occur when running this search method in a Trie if the word is not found?

DSA Python

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

A KeyError when a character is not found in children dictionary

B AttributeError because node is None

C Returns False correctly without error

D SyntaxError due to missing colon

💡 Hint

What happens if a character is missing in the children dictionary?

Accessing node.children[char] without checking if char exists causes KeyError if char is missing.

🚀 Application

advanced

Number of Words with Given Prefix in Trie

Given a Trie with words inserted, which method correctly counts how many words start with a given prefix?

DSA Python

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 count_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return self._count_words(node)

    def _count_words(self, node):
        count = 1 if node.is_end else 0
        for child in node.children.values():
            count += self._count_words(child)
        return count

A Returns the total number of words in the Trie regardless of prefix

B Returns the length of the prefix string

C Returns 1 if prefix exists, else 0

D Returns the number of words that start with the given prefix

💡 Hint

The method counts words from the node reached after prefix traversal.

The count_prefix method finds the node for the prefix, then recursively counts all words below it, giving the number of words starting with that prefix.

❓ Predict Output

expert

Output of Trie After Insertions and Searches

What is the output of this code that inserts words and searches for prefixes and words in a Trie?

DSA Python

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

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

trie = Trie()
words = ["apple", "app", "application", "bat", "batch"]
for w in words:
    trie.insert(w)

results = {
    "search_app": trie.search("app"),
    "search_appl": trie.search("appl"),
    "starts_with_app": trie.starts_with("app"),
    "starts_with_bat": trie.starts_with("bat"),
    "search_batch": trie.search("batch")
}
print(results)

A {"search_app": true, "search_appl": false, "starts_with_app": false, "starts_with_bat": true, "search_batch": true}

B {"search_app": true, "search_appl": true, "starts_with_app": true, "starts_with_bat": false, "search_batch": true}

C {"search_app": true, "search_appl": false, "starts_with_app": true, "starts_with_bat": true, "search_batch": true}

D {"search_app": false, "search_appl": false, "starts_with_app": true, "starts_with_bat": true, "search_batch": false}

💡 Hint

Search returns True only for complete words; starts_with returns True if prefix exists.

The word 'app' is inserted fully, so search("app") is True. 'appl' is a prefix but not a full word, so search("appl") is False. starts_with("app") and starts_with("bat") are True because those prefixes exist. 'batch' is inserted fully, so search("batch") is True.

Practice

1. What is the main purpose of using a Trie data structure in word search problems?

easy

A. To store words in a way that allows fast prefix-based search

B. To sort words alphabetically

C. To store words in a linked list

D. To compress words into a single string

Solution

1. Step 1: Understand the Trie structure

   A Trie stores characters of words in a tree-like structure where each node represents a character.

2. Step 2: Identify the main use in word search

   This structure allows quick lookup of words by their prefixes, making prefix-based search very efficient.

3. Final Answer:

   To store words in a way that allows fast prefix-based search -> Option A

4. Quick Check:

   Trie = fast prefix search [OK]

Hint: Trie is all about prefix search speed [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie stores words as linked lists
• Assuming Trie compresses words into strings

2. Which of the following is the correct way to check if a character ch exists as a child node in a Trie node's children dictionary named children?

easy

A. if ch in children.keys():

B. if children.has_key(ch):

C. if ch in children:

D. if children.contains(ch):

Solution

1. Step 1: Recall Python dictionary membership check

   In Python, to check if a key exists in a dictionary, use key in dict.

2. Step 2: Identify the correct syntax

   if ch in children: is the correct and most Pythonic way to check key existence.

3. Final Answer:

   if ch in children: -> Option C

4. Quick Check:

   Python dict key check = 'in' keyword [OK]

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

Common Mistakes:

• Using deprecated has_key() method
• Checking keys() explicitly which is slower
• Using non-existent contains() method

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

def search_word(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return node.is_end_of_word

# Trie nodes and root are properly initialized
result = search_word(root, 'cat')

If the Trie contains the words ['car', 'cat', 'cap'], what will be the value of result?

medium

A. None

B. False

C. KeyError

D. True

Solution

1. Step 1: Trace the search for 'cat'

   The function checks each character 'c', 'a', 't' in the Trie nodes. Since 'cat' is inserted, all characters exist and the last node marks end of word.

2. Step 2: Return the end of word flag

   Because 'cat' is a complete word in the Trie, node.is_end_of_word is True, so the function returns True.

3. Final Answer:

   True -> Option D

4. Quick Check:

   Word 'cat' found = True [OK]

Hint: If all chars found and end flag True, return True [OK]

Common Mistakes:

• Returning True without checking end_of_word flag
• Assuming partial prefix means word exists
• Confusing missing character with KeyError

4. The following code tries to search a word in a Trie but raises an error. Identify the bug:

def search_word(root, word):
    node = root
    for ch in word:
        if ch not in node:
            return False
        node = node[ch]
    return node.is_end_of_word

medium

A. Should use 'node.children[ch]' instead of 'node[ch]'

B. Both B and C are correct

C. Should check 'ch not in node.children' instead of 'ch not in node'

D. No bug, code is correct

Solution

1. Step 1: Analyze membership check

   The code checks if ch not in node, but node is an object, not a dictionary. It should check node.children.

2. Step 2: Analyze node traversal

   Similarly, node = node[ch] is incorrect; it should be node = node.children[ch] to access the child node.

3. Final Answer:

   Both B and C are correct -> Option B

4. Quick Check:

   Access children dict properly = Both fixes needed [OK]

Hint: Always access children dict, not node directly [OK]

Common Mistakes:

• Checking keys on node object instead of children dict
• Assigning node = node[ch] instead of node.children[ch]
• Ignoring attribute errors from wrong access

5. You want to find if any word in a Trie starts with a given prefix prefix. Which modification to the standard word search function below will correctly check for prefix existence?

def starts_with(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.children:
            return False
        node = node.children[ch]
    # What to return here?

hard

A. Return True immediately after loop ends

B. Return node.is_end_of_word

C. Return False if node has no children

D. Return True only if prefix length is 1

Solution

1. Step 1: Understand prefix search logic

   To check if any word starts with the prefix, we only need to confirm all prefix characters exist in the Trie.

2. Step 2: Decide return value after loop

   If all characters are found, return True immediately. We do not need to check if the node marks end of a word.

3. Final Answer:

   Return True immediately after loop ends -> Option A

4. Quick Check:

   Prefix found = True [OK]

Hint: If prefix chars found, return True regardless of word end [OK]

Common Mistakes:

• Returning is_end_of_word which fails for prefixes not full words
• Checking children existence unnecessarily
• Restricting prefix length to 1