Prefix Search Using Trie in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Insert and Search

What is the output of the following code that inserts words into a Trie and searches for a 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 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"]
for w in words:
    trie.insert(w)

print(trie.starts_with("app"))
print(trie.starts_with("bat"))
print(trie.starts_with("cat"))

A

False
False
True

B

True
False
False

C

False
True
False

D

True
True
False

💡 Hint

Check if each prefix exists by traversing the Trie nodes.

The method starts_with returns True if the prefix exists in the Trie. "app" and "bat" prefixes exist, but "cat" does not.

🧠 Conceptual

intermediate

Number of Words with Given Prefix

In a Trie storing the words ["dog", "door", "dorm", "cat"], how many words start with the prefix "do"?

A 0

B 3

C 1

D 2

💡 Hint

Count words that begin with 'do' in the list.

Words starting with "do" are "dog", "door", and "dorm" so total 3 words.

🔧 Debug

advanced

Find the Bug in Trie Search Method

What error will the following code raise when searching for prefix "car" after inserting words ["cat", "cap"]?

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 starts_with(self, prefix):
        node = self.root
        for char in prefix:
            node = node.children[char]
        return True

trie = Trie()
for w in ["cat", "cap"]:
    trie.insert(w)

print(trie.starts_with("car"))

A KeyError

B False

C AttributeError

D True

💡 Hint

Check what happens if a character is missing in children dictionary.

The code tries to access node.children[char] without checking if char exists. For prefix "car", 'r' is missing, causing a KeyError.

🚀 Application

advanced

Find All Words with Prefix Using Trie

Given a Trie with words ["tree", "trie", "algo", "assoc", "all"], which option correctly returns all words starting with prefix "tr"?

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 _dfs(self, node, prefix, words):
        if node.is_end:
            words.append(prefix)
        for char, child in node.children.items():
            self._dfs(child, prefix + char, words)

    def find_words_with_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        words = []
        self._dfs(node, prefix, words)
        return words

trie = Trie()
for w in ["tree", "trie", "algo", "assoc", "all"]:
    trie.insert(w)

print(trie.find_words_with_prefix("tr"))

A ['tree', 'trie']

B ['algo', 'assoc', 'all']

C ['tree']

D []

💡 Hint

Use DFS from the node matching the prefix to collect words.

The method finds the node for prefix "tr" and collects all words below it: "tree" and "trie".

🧠 Conceptual

expert

Trie Memory Usage Comparison

Which statement about memory usage of a Trie compared to a list of strings is correct when storing many words with common prefixes?

A Trie uses less memory because it compresses words into single nodes

B Trie uses more memory because it stores each character separately without sharing

C Trie uses less memory because common prefixes are shared in nodes

D Trie and list use the same memory because they store the same words

💡 Hint

Think about how common prefixes are stored once in a Trie.

Trie nodes share common prefixes, reducing memory compared to storing full words separately in a list.

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