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?"