Prefix Search Using Trie in DSA Python - Execution Trace

Concept Flow - Prefix Search Using Trie

Start at root node

↓

For each char in prefix

↓

Check if char child exists?

No→Prefix not found

Yes↓

Move to child node

↓

After last char

↓

Collect all words from this node

↓

Return list of words with prefix

Start from the root, follow each character of the prefix down the trie. If any character is missing, prefix not found. Otherwise, collect all words below the last node.

Execution Sample

DSA Python

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

# Insert words and search prefix

This code builds a trie node with children and end marker, used to insert words and search prefixes.

Execution Table

Step	Operation	Current Node	Character	Child Exists?	Action	Trie State (Visual)
1	Start prefix search	root	a	Yes	Move to child 'a'	root └─ a
2	Check next char	node 'a'	p	Yes	Move to child 'p'	root └─ a └─ p
3	Check next char	node 'p'	p	Yes	Move to child 'p'	root └─ a └─ p └─ p
4	Check next char	node 'p'	l	Yes	Move to child 'l'	root └─ a └─ p └─ p └─ l
5	Check next char	node 'l'	e	Yes	Move to child 'e'	root └─ a └─ p └─ p └─ l └─ e
6	Prefix end reached	node 'e'	-	-	Collect all words from here	Words found: ['apple']
7	Return result	-	-	-	Return ['apple']	Search complete

💡 Prefix fully matched; collected all words starting with prefix.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
current_node	root	node 'a'	node 'p'	node 'p'	node 'l'	node 'e'	node 'e'
character	-	a	p	p	l	e	-
words_collected	[]	[]	[]	[]	[]	[]	['apple']

Key Moments - 3 Insights

Why do we stop searching if a character child does not exist?

Because if the child node for a character in the prefix is missing (see Step 3 or 4 in execution_table), it means no word in the trie starts with that prefix, so we stop immediately.

How do we collect all words after reaching the last prefix character?

After reaching the node for the last prefix character (Step 6), we perform a traversal from that node to find all complete words (marked by is_end=True). This is why words_collected updates only at Step 6.

Why do we move current_node to the child node at each step?

Moving current_node to the child node (Steps 1-5) follows the prefix path down the trie. This ensures we check each character in order and reach the node representing the prefix end.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current_node after Step 3?

A node 'a'

B node 'l'

C node 'p' (second 'p')

D root

💡 Hint

Check the 'current_node' column for Step 3 in execution_table.

At which step does the prefix search start collecting words?

A Step 6

B Step 4

C Step 5

D Step 7

💡 Hint

Look for the row where 'Collect all words from here' is the action.

If the prefix was 'apz' instead of 'apple', what would happen at Step 3?

A Child 'z' exists, move to it

B Child 'z' does not exist, stop search

C Collect words immediately

D Restart search from root

💡 Hint

Refer to 'Child Exists?' and 'Action' columns in execution_table for missing children.

Concept Snapshot

Prefix Search Using Trie:
- Start at root node
- For each prefix char, move to child node if exists
- If any char missing, prefix not found
- After last char, collect all words below
- Returns list of words starting with prefix

Full Transcript

Prefix search in a trie starts at the root node. For each character in the prefix, we check if the child node exists. If it does, we move to that child node. If any character is missing, the prefix does not exist in the trie and we stop. Once we reach the node representing the last character of the prefix, we collect all words that start from this node by traversing its children. This process returns all words in the trie that begin with the given prefix.

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