Trie Search Operation in DSA Python

Mental Model

A trie stores words by branching letters step-by-step. Searching means following these branches letter by letter to find if a word exists.

Analogy: Imagine a tree where each branch is a letter. To find a word, you walk down the branches matching each letter until you reach the end of the word or get stuck.

root
 ↓
 [c] -> [a] -> [t*]
          ↓
         [r] -> [s*]

* means end of a word

Dry Run Walkthrough

Input: Trie with words: 'cat', 'cars'; search for 'car'

Goal: Check if 'car' exists in the trie

Step 1: Start at root node, look for child 'c'

root -> [c] -> [a] -> [t*]
               ↓
              [r] -> [s*]

Why: We must find the first letter 'c' to continue searching

Step 2: Move to node 'c', look for child 'a'

root -> c -> [a] -> [t*]
               ↓
              [r] -> [s*]

Why: Next letter 'a' must be found among children of 'c'

Step 3: Move to node 'a', look for child 'r'

root -> c -> a -> [r] -> [s*]

Why: Next letter 'r' must be found among children of 'a'

Step 4: Move to node 'r', check if this node marks end of word for 'car'

root -> c -> a -> r -> [s*]

Why: We reached last letter of 'car', check if 'car' is a complete word

Step 5: Check end marker at 'r' node; not end of word

root -> c -> a -> r -> s*

Why: 'r' node is not end of word, so 'car' is not stored as a word

Result:

root -> c -> a -> r -> s*
Answer: 'car' not found as a complete word

Annotated Code

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: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]  # advance to next letter node
        return node.is_end_of_word  # check if word ends here

# Driver code
trie = Trie()
words = ['cat', 'cars']
for w in words:
    trie.insert(w)

search_word = 'car'
found = trie.search(search_word)
print(f"{search_word} found: {found}")

node = self.root

start search from root node

if char not in node.children:

check if current letter exists in children

node = node.children[char]

advance to child node matching current letter

return node.is_end_of_word

return true only if current node marks end of word

Output

car found: False

Complexity Analysis

Time: O(m) because we check each letter of the word once during search

Space: O(1) for search as no extra space is used besides pointers

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster because it avoids checking all words

Edge Cases

searching empty string

returns False because empty word is not stored

DSA Python

return node.is_end_of_word

searching word not inserted

returns False immediately when letter missing

DSA Python

if char not in node.children: return False

searching word that is prefix but not complete word

returns False because end marker is missing

DSA Python

return node.is_end_of_word

When to Use This Pattern

When you need to quickly check if a word or prefix exists among many words, use trie search to follow letter branches efficiently.

Common Mistakes

Mistake: Returning True as soon as all letters are found without checking end of word marker
Fix: Always check if the last node marks the end of a complete word before returning True

Summary

Searches for a word by following letter nodes step-by-step in the trie.

Use when you want fast word lookup among many stored words.

The key is to check each letter in order and confirm the word ends exactly at the last letter node.

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