Autocomplete System with Trie in DSA Python - Execution Trace

Concept Flow - Autocomplete System with Trie

Start: Input prefix

↓

Traverse Trie from root

↓

For each character in prefix

↓

If character node exists?

No→No suggestions

Yes↓

Reach node for prefix

↓

Collect all words below node

↓

Return list of suggestions

The system takes a prefix, moves down the trie following each character, and then collects all words starting with that prefix.

Execution Sample

DSA Python

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

# Insert words and autocomplete prefix

This code builds a trie by inserting words and finds autocomplete suggestions for a given prefix.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat'	root -> c -> a -> t (is_word=True)	root.children['c'] created c.children['a'] created a.children['t'] created	root └─ c └─ a └─ t*
2	Insert 'car'	root -> c -> a -> t (is_word=True), a -> r (is_word=True)	c.children['a'] exists a.children['r'] created	root └─ c └─ a ├─ t* └─ r*
3	Insert 'dog'	root -> c -> a -> t (is_word=True), a -> r (is_word=True), root -> d -> o -> g (is_word=True)	root.children['d'] created d.children['o'] created o.children['g'] created	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d └─ o └─ g*
4	Autocomplete prefix 'ca'	Same as above	Traverse root -> c -> a	At node 'a': Words below: 'cat', 'car'
5	Autocomplete prefix 'do'	Same as above	Traverse root -> d -> o	At node 'o': Word below: 'dog'
6	Autocomplete prefix 'z'	Same as above	root.children['z'] does not exist	No suggestions

💡 Autocomplete stops when prefix node is found or prefix path breaks (no node).

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
root.children	{}	{'c': Node}	{'c': Node}	{'c': Node, 'd': Node}	{'c': Node, 'd': Node}	{'c': Node, 'd': Node}	{'c': Node, 'd': Node}
current_node	root	root	root	root	node at 'a'	node at 'o'	root
suggestions	[]	[]	[]	[]	['cat', 'car']	['dog']	[]

Key Moments - 3 Insights

Why do we stop traversal when a character node does not exist in the trie?

Because the prefix cannot be completed further, so no words start with that prefix. See execution_table step 6 where 'z' node is missing, so autocomplete returns no suggestions.

How do we collect all words after reaching the prefix node?

We perform a depth-first search from the prefix node to find all nodes marked as word ends. In execution_table step 4, after reaching 'a', we find 'cat' and 'car' by exploring children.

Why do we mark nodes with is_word=True?

To know which nodes represent complete words. Without this, we can't tell if a path is a full word or just a prefix. See steps 1-3 where 't', 'r', and 'g' nodes are marked to indicate words.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what are the autocomplete suggestions for prefix 'ca'?

A ['car']

B ['cat', 'car']

C ['cat']

D []

💡 Hint

Check the Visual State column at step 4 in execution_table.

At which step does the trie first contain the word 'dog'?

A Step 3

B Step 1

C Step 2

D Step 4

💡 Hint

Look at the Operation and Nodes in Trie columns to see when 'dog' is inserted.

If we try to autocomplete prefix 'z', what happens according to the execution_table?

A Returns ['z']

B Returns all words in trie

C Returns no suggestions

D Throws an error

💡 Hint

See step 6 Pointer Changes and Visual State for prefix 'z'.

Concept Snapshot

Autocomplete with Trie:
- Insert words by creating nodes for each char
- Mark end of word nodes
- To autocomplete, traverse trie by prefix chars
- If prefix path missing, no suggestions
- Else, collect all words below prefix node
- Efficient prefix search and suggestions

Full Transcript

An autocomplete system uses a trie data structure. Words are inserted by creating nodes for each character and marking the end of words. To find suggestions for a prefix, we traverse the trie following each character. If a character node is missing, no suggestions exist. Otherwise, from the prefix node, we collect all complete words by exploring child nodes. This method efficiently finds all words starting with the given prefix.

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