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

Time Complexity: Word Search in Trie

O(n)

Understanding Time Complexity

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

Specifically, how the search time changes as the word length grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code checks if a given word exists in the Trie by following nodes for each letter.

Identify Repeating Operations

• Primary operation: Loop through each character of the word.
• How many times: Exactly once per character in the word.

How Execution Grows With Input

The time grows directly with the length of the word we search for.

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

Pattern observation: The operations increase linearly as the word length increases.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows in a straight line with the word length.

Common Mistake

[X] Wrong: "Searching a word in a Trie takes constant time regardless of word length."

[OK] Correct: Each letter must be checked one by one, so longer words take more time.

Interview Connect

Knowing how Trie search scales helps you explain efficient word lookups clearly and confidently.

Self-Check

"What if the Trie stored words with uppercase letters too? How would the time complexity change?"