Trie Search Operation in DSA Python - Time & Space Complexity

Time Complexity: Trie Search Operation

O(n)

Understanding Time Complexity

We want to understand how long it takes to find a word in a trie.

How does the search time change when the word gets longer?

Scenario Under Consideration

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

This code checks if a word exists in the trie by following each letter step-by-step.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character of the word.
• How many times: Once for every letter in the word (length n).

How Execution Grows With Input

Each extra letter means one more step to check in the trie.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows directly with the word length.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows linearly with the length of the word.

Common Mistake

[X] Wrong: "Searching a word in a trie takes time proportional to the number of words stored."

[OK] Correct: The search depends only on the word length, not how many words are in the trie.

Interview Connect

Knowing trie search time helps you explain fast word lookups clearly and confidently.

Self-Check

"What if the trie stored words with a fixed maximum length? How would the time complexity change?"

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