Trie Search Operation in DSA Python - Execution Trace

Concept Flow - Trie Search Operation

Start at root node

↓

For each character in word

↓

Check if character exists in current node's children

↓

Move to child node

↓

Repeat for next character

↓

After last character, check end-of-word flag

↓

Word found

The search starts at the root and checks each character in the word step-by-step. If a character is missing, search stops. If all characters are found and the last node marks end of a word, the word exists.

Execution Sample

DSA Python

def search(root, word):
    node = root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end_of_word

This code searches for a word in a trie by moving through nodes for each character and checking if the word ends at the last node.

Execution Table

Step	Operation	Current Character	Node Children Keys	Pointer Change	Visual State
1	Start at root	-	c, a	node = root	root node with children: c → a
2	Check 'c' in children	c	c, a	node = node.children['c']	Moved to node 'c' with children: a → t
3	Check 'a' in children	a	a, t	node = node.children['a']	Moved to node 'a' with children: t
4	Check 't' in children	t	t	node = node.children['t']	Moved to node 't' with children: ∅
5	Check end-of-word flag	-	-	-	Node 't' is end of word: True
6	Result	-	-	-	Word 'cat' found: True
7	Start at root	-	c, a	node = root	root node with children: c → a
8	Check 'c' in children	c	c, a	node = node.children['c']	Moved to node 'c' with children: a → t
9	Check 'a' in children	a	a, t	node = node.children['a']	Moved to node 'a' with children: t
10	Check 'r' in children	r	t	Not found	Character 'r' not found, stop search
11	Result	-	-	-	Word 'car' found: False

💡 Search stops when a character is not found in current node's children or after checking end-of-word flag at last character.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 10	Final
node	root	node for 'c'	node for 'a'	node for 't'	node for 'a'	node for 't' ('cat'), node for 'a' ('car')
current_character	-	c	a	t	r	-
search_result	-	-	-	-	-	True for 'cat', False for 'car'

Key Moments - 3 Insights

Why does the search stop immediately when a character is not found in the children?

Because the trie stores words as paths of characters, missing a character means the word cannot be formed. See execution_table row 10 where 'r' is missing, so search stops.

Why do we check the end-of-word flag after the last character?

Because a path may exist for the characters but not mark a complete word. The flag confirms the word ends here. See execution_table row 5 where 't' node's flag is True, confirming 'cat' exists.

What happens if we search for a prefix but not a full word?

The search will find all characters but fail at the end-of-word check, returning False.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which node does the pointer move to?

A Node for character 't'

B Root node

C Node for character 'a'

D Node for character 'c'

💡 Hint

Check the 'Pointer Change' and 'Visual State' columns at step 4 in execution_table.

At which step does the search fail for the word 'car'?

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look for the step where 'r' is not found in node children in execution_table.

If the end-of-word flag was False at step 5, what would be the search result for 'cat'?

A True

B False

C Search would continue

D Error

💡 Hint

Refer to the explanation in key_moments about the importance of the end-of-word flag.

Concept Snapshot

Trie Search Operation:
- Start at root node
- For each character, move to child node if exists
- If character missing, stop: word not found
- After last character, check end-of-word flag
- If flag True, word found; else not found

Full Transcript

Trie search starts at the root node and checks each character of the word in order. For each character, it looks for a child node matching that character. If the child node exists, the search moves to that node. If not, the search stops and returns False because the word cannot be formed. After all characters are found, the search checks if the last node marks the end of a word. If yes, the word exists in the trie; otherwise, it does not. This process ensures efficient word lookup by following paths of characters.

Practice

1. What does the search operation in a Trie data structure check for?

easy

A. If a given word exists completely in the Trie

B. If a given prefix exists in the Trie

C. If the Trie is empty

D. If the Trie contains duplicate words

Solution

1. Step 1: Understand the purpose of search in Trie

   The search operation checks if the exact word is stored in the Trie, not just a prefix.

2. Step 2: Differentiate between search and prefix check

   While prefix check looks for any starting sequence, search requires the full word to be present and marked as an end of word.

3. Final Answer:

   If a given word exists completely in the Trie -> Option A

4. Quick Check:

   Search = full word check [OK]

Hint: Search checks full word presence, not just prefix [OK]

Common Mistakes:

• Confusing search with prefix check
• Thinking search returns true for partial matches
• Assuming search checks for duplicates

2. Which of the following is the correct way to check if a character node exists in a Trie during search in Python?

easy

A. if char in current_node.children:

B. if current_node.children.contains(char):

C. if current_node.children.has_key(char):

D. if char.exists_in(current_node.children):

Solution

1. Step 1: Recall Python dictionary membership syntax

   Trie children are usually stored in a dictionary. To check if a key exists, use key in dict.

2. Step 2: Evaluate each option

   if char in current_node.children: uses correct Python syntax. Options A, B, and C use invalid or non-existent methods in Python dictionaries.

3. Final Answer:

   if char in current_node.children: -> Option A

4. Quick Check:

   Use 'in' keyword for dict keys [OK]

Hint: Use 'in' keyword to check dictionary keys in Python [OK]

Common Mistakes:

• Using non-existent dictionary methods
• Confusing syntax with other languages
• Trying to call methods on dict keys

3. What will be the output of the following code snippet?

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(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

trie = Trie()
trie.insert('cat')
print(trie.search('cat'))
print(trie.search('ca'))
print(trie.search('bat'))

medium

A. False\nFalse\nFalse

B. True\nTrue\nFalse

C. True\nFalse\nTrue

D. True\nFalse\nFalse

Solution

1. Step 1: Insert 'cat' into the Trie

   The word 'cat' is inserted, marking the last node's is_end as True.

2. Step 2: Search for 'cat', 'ca', and 'bat'

   'cat' exists fully with is_end True, so returns True. 'ca' is prefix but not a full word, so returns False. 'bat' is not inserted, so returns False.

3. Final Answer:

   True False False -> Option D

4. Quick Check:

   Full word present = True, prefix only = False [OK]

Hint: Search returns True only if full word and is_end True [OK]

Common Mistakes:

• Assuming prefix search returns True
• Not setting is_end flag on insert
• Confusing missing words with prefixes

4. Identify the error in the following Trie search method and select the fix:

def search(self, word):
    node = self.root
    for char in word:
        if char in node.children:
            node = node.children[char]
        else:
            return False
    return True

medium

A. Change 'if char in node.children' to 'if char not in node.children'

B. Return node.is_end instead of True at the end

C. Initialize node as None before loop

D. Add a break statement inside the loop

Solution

1. Step 1: Analyze the return statement

   The method returns True after traversing all characters, but it should confirm the word ends here by checking is_end flag.

2. Step 2: Correct the return value

   Return node.is_end to ensure the word is complete in the Trie, not just a prefix.

3. Final Answer:

   Return node.is_end instead of True at the end -> Option B

4. Quick Check:

   Check is_end flag to confirm full word [OK]

Hint: Always check is_end flag after traversal [OK]

Common Mistakes:

• Returning True without checking is_end
• Incorrect if condition reversing
• Unnecessary break statements

5. You want to implement a search in a Trie that returns True if the word exists or if any word in the Trie starts with the given prefix. Which modification to the standard search method achieves this?

hard

A. Return node.is_end only after traversal

B. Return False if any character is missing during traversal

C. Return True after traversing all characters without checking is_end

D. Return True only if the prefix length equals the word length

Solution

1. Step 1: Understand the difference between full word and prefix search

   Full word search requires is_end True; prefix search only requires traversal success.

2. Step 2: Modify return to support prefix search

   Return True after successfully traversing all characters without checking is_end to allow prefix matches.

3. Final Answer:

   Return True after traversing all characters without checking is_end -> Option C

4. Quick Check:

   Prefix search = True if traversal succeeds [OK]

Hint: For prefix search, ignore is_end flag, return True if path exists [OK]

Common Mistakes:

• Checking is_end for prefix search
• Returning False prematurely
• Confusing prefix length with word length