Trie Insert Operation in DSA Typescript - Time & Space Complexity

Time Complexity: Trie Insert Operation

O(m)

Understanding Time Complexity

We want to understand how the time to add a word to a trie grows as the word gets longer.

How does the number of steps change when the word length increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class TrieNode {
  children: Map = new Map();
  isEndOfWord: boolean = false;
}

function insert(root: TrieNode, word: string): void {
  let node = root;
  for (const char of word) {
    if (!node.children.has(char)) {
      node.children.set(char, new TrieNode());
    }
    node = node.children.get(char)!;
  }
  node.isEndOfWord = true;
}
    

This code adds 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 word.
• How many times: Exactly once per character in the word (word length).

How Execution Grows With Input

Each added character means one more step in the loop, so the work grows directly with word length.

Input Size (word length)	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(m)

This means the time to insert depends directly on the length of the word being added.

Common Mistake

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

[OK] Correct: The insert only loops through the new word's characters, not all stored words, so existing size doesn't affect insert time.

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 data structure to use an array of fixed size 26 for children instead of a map? How would the time complexity change?