Prefix Search Using Trie in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the trie.

DSA Python

def insert_word(root, word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[[1]] = TrieNode()
        node = node.children[char]

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

Aroot

Bword

Cchar

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole word instead of the current character.

Using the root or node variable incorrectly as a key.

We use the current character 'char' as the key to add a new child node in the trie.

2fill in blank

medium

Complete the code to check if a prefix exists in the trie.

DSA Python

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

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

Achar

Bprefix

Cnode

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Checking the whole prefix instead of the current character.

Using the wrong variable to check children.

We check if the current character 'char' is in the children of the current node.

3fill in blank

hard

Fix the error in the code to mark the end of a word in the trie.

DSA Python

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

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

Aend_of_word

Bis_end_of_word

Cis_word_end

Dword_end

Attempts:

3 left

💡 Hint

Common Mistakes

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

Forgetting to mark the end of the word.

The standard attribute to mark the end of a word is 'is_end_of_word'.

4fill in blank

hard

Fill both blanks to complete the search function that returns True if a word exists in the trie.

DSA Python

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

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

Achar

Bword

Cnode

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for checking and accessing children.

Using the whole word or wrong variables instead of the current character.

We check and access the child node using the current character 'char' in the word.

5fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each word to True if it starts with the prefix.

DSA Python

result = {word{BLANK_1}}: True for word in words if word{{BLANK_2}} prefix:

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

A[:len(prefix)]

B==

C:

Din

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'in' instead of equality for prefix check.

Incorrect slicing syntax.

We slice the word up to the prefix length and check if it equals the prefix, then map word to True.

Practice

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

easy

A. To perform arithmetic operations quickly

B. To sort words alphabetically

C. To store numbers in sorted order

D. To efficiently find all words starting with a given prefix

Solution

1. Step 1: Understand Trie usage

   A Trie stores characters of words in a tree structure, allowing quick prefix lookups.

2. Step 2: Identify prefix search goal

   Prefix search means finding all words that start with a given prefix efficiently.

3. Final Answer:

   To efficiently find all words starting with a given prefix -> Option D

4. Quick Check:

   Trie = prefix search efficiency [OK]

Hint: Trie nodes represent prefixes for fast search [OK]

Common Mistakes:

• Confusing Trie with sorting data structure
• Thinking Trie is for arithmetic
• Assuming Trie stores whole words only

2. Which of the following is the correct way to insert a word into a Trie node in Python?

easy

A. node.children.add(char)

B. node.children[char] = TrieNode() if char not in node.children else node.children[char]

C. node.children.append(char)

D. node.children[char] = char

Solution

1. Step 1: Understand Trie children structure

   Trie children are usually stored in a dictionary mapping characters to TrieNode objects.

2. Step 2: Correct insertion syntax

   We check if character exists; if not, create new TrieNode and assign it to children dictionary.

3. Final Answer:

   node.children[char] = TrieNode() if char not in node.children else node.children[char] -> Option B

4. Quick Check:

   Insert word by mapping char to TrieNode [OK]

Hint: Use dictionary keys for children, not list methods [OK]

Common Mistakes:

• Using list methods like append or add on dictionary
• Assigning character instead of TrieNode
• Not checking if child node exists before insertion

3. Given the following code snippet, what will be the output of trie.starts_with('app')?

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 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()
trie.insert('apple')
trie.insert('app')
print(trie.starts_with('app'))

medium

A. Error

B. False

C. True

D. None

Solution

1. Step 1: Insert words 'apple' and 'app'

   Both words share prefix 'app', so nodes for 'a', 'p', 'p' exist in Trie.

2. Step 2: Check starts_with('app')

   Function checks each character in 'app' exists in children; all found, so returns True.

3. Final Answer:

   True -> Option C

4. Quick Check:

   Prefix 'app' exists in Trie = True [OK]

Hint: If prefix nodes exist, starts_with returns True [OK]

Common Mistakes:

• Confusing starts_with with full word search
• Expecting False because 'app' is prefix, not full word
• Ignoring that 'app' was inserted

4. Identify the bug in the following Trie starts_with method and select the correct fix:

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

medium

A. Return False inside else, return True after loop

B. Return True inside else, return True after loop

C. Return False inside else, return False after loop

D. Return True inside else, return False after loop

Solution

1. Step 1: Analyze current else return

   Currently, if char not found, method returns True incorrectly; should return False.

2. Step 2: Correct return values

   Return False inside else (prefix not found), and True after loop (prefix fully matched).

3. Final Answer:

   Return False inside else, return True after loop -> Option A

4. Quick Check:

   Prefix missing = False, prefix found = True [OK]

Hint: Return False if char missing, True if all found [OK]

Common Mistakes:

• Returning True when prefix char missing
• Returning False after loop instead of True
• Confusing else and after loop returns

5. You want to find all words in a Trie that start with the prefix "car". Which approach correctly extends the prefix search to list all such words?

hard

A. Traverse to node of 'car' prefix, then recursively collect all words from that node

B. Search each word in Trie and check if it starts with 'car' using string slicing

C. Insert 'car' as a word and then search for it

D. Use a hash map to store all words and filter by prefix

Solution

1. Step 1: Locate prefix node in Trie

   Traverse Trie nodes for 'c', 'a', 'r' to reach prefix node.

2. Step 2: Recursively collect words from prefix node

   From prefix node, explore all child nodes to build and collect complete words starting with 'car'.

3. Final Answer:

   Traverse to node of 'car' prefix, then recursively collect all words from that node -> Option A

4. Quick Check:

   Prefix node + recursion = all words with prefix [OK]

Hint: Find prefix node, then DFS to collect words [OK]

Common Mistakes:

• Checking all words instead of using Trie structure
• Inserting prefix as word incorrectly
• Using unrelated data structures like hash map