Prefix matching with tries in Data Structures Theory - Mini Project: Build & Apply

Prefix Matching with Tries

📖 Scenario: Imagine you are building a simple phone contact search system. When a user types the first few letters of a name, the system should quickly find all contacts that start with those letters.

🎯 Goal: You will build a basic trie data structure step-by-step to store contact names and then find all names that start with a given prefix.

📋 What You'll Learn

Create a trie node structure to hold children and end-of-word marker

Add a configuration variable to hold the root of the trie

Insert a list of contact names into the trie

Implement a prefix search function to find all contacts starting with a given prefix

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and contact lists to quickly find words or names starting with certain letters.

💼 Career

Understanding tries helps in software development roles involving search optimization, text processing, and building efficient data structures.

1

Create the Trie Node Structure

Create a class called TrieNode with an __init__ method that initializes two attributes: children as an empty dictionary and is_end_of_word as False.

Data Structures Theory

# Your code here

Hint

Think of each node as a letter holder with links to next letters and a flag to mark if a word ends here.

2

Create the Trie Root Node

Create a variable called root and assign it a new instance of TrieNode().

Data Structures Theory

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

# Your code here

Hint

The root node is the starting point of the trie. It does not hold a letter itself.

3

Insert Contact Names into the Trie

Create a function called insert that takes a word string and inserts it into the trie starting from the root. Use a for loop with variable char to iterate over each character in word. For each character, if it is not in current.children, add a new TrieNode(). Move current to the child node for that character. After the loop, set current.is_end_of_word to True. Then, insert the names "Anna", "Anne", and "Annie" by calling insert for each.

Data Structures Theory

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

root = TrieNode()

# Your code here

Hint

Each character creates or moves to a child node. Mark the end of the word after inserting all characters.

4

Implement Prefix Search Function

Create a function called search_prefix that takes a prefix string and returns a list of all words in the trie that start with that prefix. First, use a for loop with variable char to traverse the trie from root following the prefix characters. If a character is missing, return an empty list. Then, define a helper function dfs that takes a node and path string and recursively collects all words starting from that node. Use dfs to collect and return all matching words with the prefix.

Data Structures Theory

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

root = TrieNode()

def insert(word):
    current = root
    for char in word:
        if char not in current.children:
            current.children[char] = TrieNode()
        current = current.children[char]
    current.is_end_of_word = True

insert("Anna")
insert("Anne")
insert("Annie")

# Your code here

Hint

First find the node matching the prefix, then explore all words below it using depth-first search.

Practice

1. What is the main advantage of using a trie for prefix matching?

easy

A. It stores words in reverse order

B. It uses less memory than arrays

C. It sorts words alphabetically automatically

D. It allows fast lookup of words sharing common prefixes

Solution

1. Step 1: Understand trie structure

   A trie stores words by sharing nodes for common prefixes, reducing repeated storage.

2. Step 2: Identify prefix matching benefit

   This structure allows quick traversal to find all words starting with a given prefix.

3. Final Answer:

   It allows fast lookup of words sharing common prefixes -> Option D

4. Quick Check:

   Prefix matching speed = Fast lookup [OK]

Hint: Tries speed up prefix search by sharing nodes [OK]

Common Mistakes:

• Confusing tries with hash tables
• Thinking tries sort words automatically
• Assuming tries store words backwards

2. Which of the following is the correct way to check if a prefix exists in a trie?

easy

A. Search the entire trie for the full word

B. Traverse nodes matching each prefix character until end or mismatch

C. Count all leaf nodes in the trie

D. Sort all words and do binary search

Solution

1. Step 1: Understand prefix search in tries

   To check a prefix, we walk down the trie nodes matching each character in order.

2. Step 2: Identify correct method

   If traversal completes without mismatch, prefix exists; otherwise, it does not.

3. Final Answer:

   Traverse nodes matching each prefix character until end or mismatch -> Option B

4. Quick Check:

   Prefix check = Node traversal [OK]

Hint: Walk trie nodes character by character for prefix [OK]

Common Mistakes:

• Searching entire trie instead of prefix path
• Counting leaf nodes unrelated to prefix
• Using sorting instead of trie traversal

3. Given a trie containing words: ['cat', 'car', 'cart', 'dog'], which words match the prefix 'car'?

medium

A. ['car', 'cart']

B. ['dog']

C. ['cat', 'car']

D. ['cat', 'dog']

Solution

1. Step 1: Identify words starting with 'car'

   From the list, 'car' and 'cart' start with the prefix 'car'.

2. Step 2: Exclude words not matching prefix

   'cat' starts with 'cat', not 'car'; 'dog' does not match prefix.

3. Final Answer:

   ['car', 'cart'] -> Option A

4. Quick Check:

   Words with prefix 'car' = ['car', 'cart'] [OK]

Hint: Match prefix exactly to filter words [OK]

Common Mistakes:

• Including words with similar but different prefixes
• Confusing 'cat' with 'car'
• Selecting unrelated words

4. A trie implementation returns false when checking prefix 'app' even though words ['apple', 'application'] exist. What is the most likely error?

medium

A. The trie nodes for 'app' were not linked correctly

B. The words were inserted backwards

C. The prefix check is case-insensitive

D. The trie only stores full words, not prefixes

Solution

1. Step 1: Analyze prefix check failure

   If words with prefix 'app' exist but check fails, likely the path for 'app' nodes is broken.

2. Step 2: Exclude other causes

   Words inserted backwards or case issues would cause different errors; tries store prefixes inherently.

3. Final Answer:

   The trie nodes for 'app' were not linked correctly -> Option A

4. Quick Check:

   Broken node links = prefix check fail [OK]

Hint: Check node links for prefix path [OK]

Common Mistakes:

• Assuming tries don't store prefixes
• Ignoring node linkage errors
• Confusing case sensitivity issues

5. You want to build an autocomplete feature using a trie. Which approach best improves performance when many words share prefixes?

hard

A. Use a linked list instead of trie nodes for each character

B. Store full words only at leaf nodes without intermediate nodes

C. Store a count of words passing through each node to quickly find popular prefixes

D. Sort all words and do linear search for each prefix

Solution

1. Step 1: Understand autocomplete with tries

   Autocomplete benefits from knowing how many words share a prefix to prioritize suggestions.

2. Step 2: Identify performance improvement

   Storing counts at each node helps quickly find popular prefixes without full traversal.

3. Final Answer:

   Store a count of words passing through each node to quickly find popular prefixes -> Option C

4. Quick Check:

   Node counts = faster autocomplete [OK]

Hint: Count words at nodes to speed autocomplete [OK]

Common Mistakes:

• Storing words only at leaves slows prefix search
• Using linked lists reduces trie efficiency
• Linear search ignores trie benefits