Autocomplete System with Trie in DSA Python - Build from Scratch

Autocomplete System with Trie

📖 Scenario: You are building a simple autocomplete system like the ones used in search engines or messaging apps. When a user types a few letters, the system suggests words that start with those letters.To do this efficiently, you will use a Trie data structure, which stores words in a tree-like form where each node represents a letter.

🎯 Goal: Build a Trie to store a list of words and then find all words that start with a given prefix.This will help you understand how autocomplete systems work behind the scenes.

📋 What You'll Learn

Create a Trie node class with children and end-of-word marker

Insert given words into the Trie

Search the Trie for all words starting with a given prefix

Print the list of autocomplete suggestions

💡 Why This Matters

🌍 Real World

Autocomplete systems are used in search engines, messaging apps, and code editors to help users type faster by suggesting possible completions.

💼 Career

Understanding Tries and autocomplete logic is useful for software engineers working on search features, text input optimization, and user experience improvements.

1

Create the Trie Node class and insert words

Create a class called TrieNode with an attribute children as an empty dictionary and is_end_of_word as False. Then create a class called Trie with a root node of type TrieNode. Finally, write a method insert in Trie that takes a word and inserts it letter by letter into the Trie. Insert these exact words into the Trie: 'cat', 'car', 'cart', 'dog', 'dove'.

DSA Python

# Define TrieNode and Trie classes
# Insert the words 'cat', 'car', 'cart', 'dog', 'dove' into the Trie
# Your code here

Hint

Think of the Trie as a tree where each letter is a branch. Insert each letter of the word step by step, creating new branches if needed.

2

Add a method to search for the node matching a prefix

In the Trie class, add a method called search_prefix that takes a string prefix and returns the node where this prefix ends in the Trie. If the prefix does not exist, return None. Use a for loop with variable letter to traverse the Trie starting from self.root.

DSA Python

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for letter in word:
            if letter not in node.children:
                node.children[letter] = TrieNode()
            node = node.children[letter]
        node.is_end_of_word = True

trie = Trie()
words = ['cat', 'car', 'cart', 'dog', 'dove']
for word in words:
    trie.insert(word)

# Add a method called search_prefix that takes prefix and returns the node where prefix ends or None
# Your code here

Hint

Start from the root and follow each letter of the prefix. If any letter is missing, return None. Otherwise, return the last node reached.

3

Add a method to collect all words from a given node

In the Trie class, add a method called collect_words that takes a node and a prefix string. It should return a list of all words in the Trie that start with the given prefix by exploring all children recursively. Use a helper function inside collect_words called dfs that takes a current_node and current_prefix. If current_node.is_end_of_word is True, add current_prefix to the results list. Then recursively call dfs on each child letter and node. Finally, return the results list.

DSA Python

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for letter in word:
            if letter not in node.children:
                node.children[letter] = TrieNode()
            node = node.children[letter]
        node.is_end_of_word = True

    def search_prefix(self, prefix):
        node = self.root
        for letter in prefix:
            if letter not in node.children:
                return None
            node = node.children[letter]
        return node

trie = Trie()
words = ['cat', 'car', 'cart', 'dog', 'dove']
for word in words:
    trie.insert(word)

# Add a method called collect_words that returns all words starting from a node with a prefix
# Your code here

Hint

Use a small helper function to explore all paths from the node. Add words to the list when you reach the end of a word.

4

Find and print autocomplete suggestions for a prefix

Use the search_prefix method on trie with the prefix 'car' and store the result in prefix_node. If prefix_node is not None, call collect_words with prefix_node and 'car' to get a list of suggestions. Print the list of suggestions exactly as returned.

DSA Python

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for letter in word:
            if letter not in node.children:
                node.children[letter] = TrieNode()
            node = node.children[letter]
        node.is_end_of_word = True

    def search_prefix(self, prefix):
        node = self.root
        for letter in prefix:
            if letter not in node.children:
                return None
            node = node.children[letter]
        return node

    def collect_words(self, node, prefix):
        results = []
        def dfs(current_node, current_prefix):
            if current_node.is_end_of_word:
                results.append(current_prefix)
            for letter, child_node in current_node.children.items():
                dfs(child_node, current_prefix + letter)
        dfs(node, prefix)
        return results

trie = Trie()
words = ['cat', 'car', 'cart', 'dog', 'dove']
for word in words:
    trie.insert(word)

# Use search_prefix with 'car' and print the autocomplete suggestions
# Your code here

Hint

Find the node for 'car' and then collect all words starting from there. Print the list exactly as returned.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To sort words alphabetically

B. To efficiently store and search prefixes of words

C. To count the total number of words

D. To encrypt the stored words

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie is a tree-like data structure designed to store strings by their prefixes, allowing quick prefix-based searches.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires finding all words starting with a given prefix efficiently, which Trie supports by traversing nodes matching the prefix.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option B

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie stores prefixes for fast autocomplete search [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with hash tables
• Assuming Trie encrypts data

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

easy

A. node['c'] = TrieNode()

B. node.insert('c')

C. node.add('c')

D. node.children['c'] = TrieNode()

Solution

1. Step 1: Understand Trie node structure

   Trie nodes typically have a dictionary called children to map characters to child nodes.

2. Step 2: Insert character as a key in children dictionary

   To insert 'c', assign a new TrieNode to node.children['c'].

3. Final Answer:

   node.children['c'] = TrieNode() -> Option D

4. Quick Check:

   Insert char in children dict = node.children['c'] = TrieNode() [OK]

Hint: Use children dictionary to add new character nodes [OK]

Common Mistakes:

• Trying to assign directly to node['c'] without children
• Using non-existent methods like add or insert
• Confusing list with dictionary for children

3. Given the following code snippet, what will be the output?

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_prefix(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('dog')
trie.insert('deer')
print(trie.search_prefix('de'))
print(trie.search_prefix('do'))
print(trie.search_prefix('da'))

medium

A. True\nFalse\nFalse

B. False\nTrue\nFalse

C. True\nTrue\nFalse

D. False\nFalse\nFalse

Solution

1. Step 1: Insert words 'dog' and 'deer' into Trie

   Both words add nodes for their characters. 'dog' adds d->o->g, 'deer' adds d->e->e->r.

2. Step 2: Check prefixes 'de', 'do', and 'da'

   'de' exists as prefix in 'deer', so returns True. 'do' exists as prefix in 'dog', so True. 'da' does not exist, so False.

3. Final Answer:

   True True False -> Option C

4. Quick Check:

   Prefix 'de' and 'do' found, 'da' not found = True, True, False [OK]

Hint: Check prefix path existence in Trie children [OK]

Common Mistakes:

• Confusing search_prefix with full word search
• Assuming 'da' prefix exists
• Ignoring is_end flag for prefix search

4. The following code is intended to insert words into a Trie, but it raises an error. What is the error?

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]

medium

A. TypeError: list indices must be integers or slices, not str

B. AttributeError: 'TrieNode' object has no attribute 'children'

C. SyntaxError: invalid syntax

D. No error, code runs fine

Solution

1. Step 1: Identify data structure used for children

   The code uses a list for children, but tries to access it with string keys.

2. Step 2: Understand list indexing rules

   Lists require integer indices, but code uses node.children[char] where char is a string, causing TypeError.

3. Final Answer:

   TypeError: list indices must be integers or slices, not str -> Option A

4. Quick Check:

   Using list with string keys causes TypeError [OK]

Hint: Use dictionary, not list, for children to index by characters [OK]

Common Mistakes:

• Using list instead of dict for children
• Ignoring error message details
• Assuming code runs without error

5. You want to implement an autocomplete system that returns all words starting with a given prefix using a Trie. Which approach correctly collects all matching words after reaching the prefix node?

hard

A. Perform a depth-first search (DFS) from the prefix node, collecting words where is_end is True

B. Return all children keys of the prefix node without further traversal

C. Only return the prefix itself without searching deeper

D. Use breadth-first search (BFS) but ignore is_end flags

Solution

1. Step 1: Reach the node matching the prefix

   Traverse the Trie to the node representing the last character of the prefix.

2. Step 2: Collect all words starting from prefix node using DFS

   Use DFS to explore all child nodes recursively, collecting words where is_end is True to get complete words.

3. Final Answer:

   Perform a depth-first search (DFS) from the prefix node, collecting words where is_end is True -> Option A

4. Quick Check:

   DFS from prefix node with is_end check = correct autocomplete [OK]

Hint: Use DFS from prefix node, collect words at is_end True [OK]

Common Mistakes:

• Returning only immediate children keys
• Ignoring is_end flags and returning incomplete words
• Using BFS without checking word ends