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

Time Complexity: Trie Insert Operation

O(n)

Understanding Time Complexity

We want to understand how the time to insert a word into a trie changes as the word gets longer.

How does the number of steps grow when adding more letters?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

void insert(TrieNode* root, const std::string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int index = c - 'a';
        if (!node->children[index])
            node->children[index] = new TrieNode();
        node = node->children[index];
    }
    node->isEnd = true;
}
    

This code inserts each letter of a word into the trie, creating new nodes if needed.

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 letter in the word (word length = n).

How Execution Grows With Input

Each letter causes one step to check or create a node, so the steps grow directly with word length.

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

Pattern observation: The time grows linearly as the word gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows in direct proportion to the length of the word.

Common Mistake

[X] Wrong: "Insertion time depends on the number of words already in the trie."

[OK] Correct: The insertion only depends on the length of the word being added, not how many words are stored.

Interview Connect

Knowing this helps you explain why tries are efficient for prefix searches and insertions, a common topic in coding interviews.

Self-Check

"What if we changed the alphabet size from 26 to 256? How would the time complexity change?"