Prefix Search Using Trie 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 from the root to leaves represent words.

beginner

How does a Trie help in prefix search?

A Trie allows quick prefix search by following the path of characters in the prefix from the root. If the path exists, all words under that node share the prefix.

intermediate

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

The time complexity is O(m), where m is the length of the prefix. This is because we only traverse nodes corresponding to the prefix characters.

beginner

Explain the role of the 'is_end_of_word' flag in a Trie node.

The 'is_end_of_word' flag marks if a node represents the end of a valid word. It helps distinguish between prefixes and complete words during search.

beginner

What happens if a prefix does not exist in the Trie during a search?

If the prefix path does not exist in the Trie, the search returns no results, meaning no words in the Trie start with that prefix.

What does each node in a Trie typically represent?

A A whole word

B An integer value

C A character of a string

D A number of children

Each node in a Trie represents a single character of a string.

What is the main advantage of using a Trie for prefix search?

A Faster prefix lookup by traversing characters

B Uses less memory than arrays

C Stores numbers efficiently

D Sorts words automatically

Trie allows fast prefix lookup by following character paths.

If a prefix is not found in a Trie, what is the result?

A No words with that prefix exist

B All words are returned

C The Trie is rebuilt

D The search continues in a linked list

If prefix path is missing, no words with that prefix exist.

What does the 'is_end_of_word' flag indicate in a Trie node?

A Number of children nodes

B End of a valid word

C Start of a word

D Depth of the node

'is_end_of_word' marks the node as the end of a valid word.

What is the time complexity to search for a prefix of length m in a Trie?

A O(m^2)

B O(n)

C O(log m)

D O(m)

Searching a prefix takes O(m) time, where m is prefix length.

Describe how a Trie is used to perform prefix search.

Think about following characters from root to find prefix.

Explain the structure of a Trie node and its role in prefix search.

Focus on what each node stores and how it connects.

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