Trie Insert Operation in DSA Go - 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 we add longer words?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func (t *TrieNode) Insert(word string) {
    node := t
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character of the input word.
• How many times: Exactly once for each character in the word (length n).

How Execution Grows With Input

Each character in the word requires one step to check or create a node.

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

Pattern observation: The steps grow directly with the word length, so doubling the word doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows linearly with the length of the word.

Common Mistake

[X] Wrong: "Inserting a word takes constant time because we just add nodes once."

[OK] Correct: Each character must be processed, so longer words take more time, not the same time.

Interview Connect

Understanding this helps you explain how tries efficiently handle many words, especially when words share prefixes.

Self-Check

"What if we changed the data structure for children from a map to a fixed-size array? How would the time complexity change?"