Trie Search Operation in DSA C++ - Time & Space Complexity

Time Complexity: Trie Search Operation

O(n)

Understanding Time Complexity

We want to know how long it takes to find a word in a Trie data structure.

The question is: how does the search time grow as the word length changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool search(TrieNode* root, const std::string& word) {
    TrieNode* node = root;
    for (char c : word) {
        if (!node->children[c - 'a']) {
            return false;
        }
        node = node->children[c - 'a'];
    }
    return node->isEndOfWord;
}
    

This code checks if a given word exists in the Trie by following each character's path.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each character in the word.
• How many times: Exactly once per character in the word (word length).

How Execution Grows With Input

As the word gets longer, the search checks more characters one by one.

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

Pattern observation: The number of operations 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 you are looking for.

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 length of the word, not how many words are in the Trie.

Interview Connect

Knowing Trie search time helps you explain efficient word lookups, a common task in coding problems.

Self-Check

"What if the Trie stored uppercase and lowercase letters separately? How would the time complexity change?"

Practice

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

easy

A. Checks if a given word exists in the Trie

B. Deletes a word from the Trie

C. Inserts a new word into the Trie

D. Counts the total words stored in the Trie

Solution

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

   The search operation is designed to check if a specific word is present in the Trie structure.

2. Step 2: Differentiate from other operations

   Insertion adds words, deletion removes words, and counting totals words. Search only checks existence.

3. Final Answer:

   Checks if a given word exists in the Trie -> Option A

4. Quick Check:

   Trie search = check word presence [OK]

Hint: Search checks presence of word, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert operation
• Thinking search deletes words
• Assuming search counts words

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

easy

A. if (node->children[ch])

B. if (node->children[ch] == nullptr)

C. if (node->children[ch] != nullptr)

D. if (node->children.find(ch) != node->children.end())

Solution

1. Step 1: Understand Trie children representation

   Trie children are usually stored in a map or unordered_map. To check existence, use find() method.

2. Step 2: Identify correct syntax for existence check

   Using find(ch) != end() confirms if character node exists without creating new nodes.

3. Final Answer:

   if (node->children.find(ch) != node->children.end()) -> Option D

4. Quick Check:

   Use find() to check key existence in map [OK]

Hint: Use find() != end() to check map key existence safely [OK]

Common Mistakes:

• Using node->children[ch] != nullptr causes insertion
• Accessing children[ch] directly creates new node
• Checking children[ch] == nullptr can cause insertion

3. Consider the following C++ Trie search code snippet:

bool search(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char ch : word) {
        if (node->children.find(ch) == node->children.end())
            return false;
        node = node->children[ch];
    }
    return node->isEndOfWord;
}

What will be the output of search(root, "cat") if the Trie contains words: "car", "cat", "cap"?

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Trace search for "cat" in Trie

   Each character 'c', 'a', 't' is found in children nodes. The loop completes without returning false.

2. Step 2: Check isEndOfWord flag at last node

   Since "cat" is inserted, the last node's isEndOfWord is true, so function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Word "cat" exists in Trie = true [OK]

Hint: If all chars found and isEndOfWord true, search returns true [OK]

Common Mistakes:

• Ignoring isEndOfWord flag and returning true prematurely
• Assuming partial match means word exists
• Confusing false return with missing character

4. Identify the bug in the following Trie search function:

bool search(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char ch : word) {
        if (node->children[ch] == nullptr)
            return false;
        node = node->children[ch];
    }
    return node->isEndOfWord;
}

medium

A. Missing check for empty word input

B. Using node->children[ch] in if condition inserts new nodes unintentionally

C. Incorrect return type for search function

D. Loop variable should be int, not char

Solution

1. Step 1: Analyze children access in if condition

   Accessing node->children[ch] creates a new node if it doesn't exist, which is wrong during search.

2. Step 2: Correct way to check existence

   Use find() method to check if child exists without creating new nodes.

3. Final Answer:

   Using node->children[ch] in if condition inserts new nodes unintentionally -> Option B

4. Quick Check:

   Accessing map key directly creates nodes [OK]

Hint: Use find() to check existence, not direct map access [OK]

Common Mistakes:

• Using direct map access in condition causing side effects
• Ignoring empty string edge case
• Wrong loop variable type

5. You have a Trie storing the words: "apple", "app", "application", "bat", "batch". Which of the following search queries will return false?

hard

A. "batch"

B. "app"

C. "appl"

D. "bat"

Solution

1. Step 1: Check if "appl" is a complete word in Trie

   "appl" is a prefix of "apple" and "application" but not a complete word, so isEndOfWord is false.

2. Step 2: Verify other words

   "app", "batch", and "bat" are all complete words stored in the Trie, so search returns true for them.

3. Final Answer:

   "appl" -> Option C

4. Quick Check:

   Prefix only, not full word = false [OK]

Hint: Search returns false for prefixes not marked as words [OK]

Common Mistakes:

• Assuming prefix is always found as word
• Ignoring isEndOfWord flag
• Confusing similar words with exact matches