Trie Insert Operation in DSA Javascript - Time & Space Complexity

Time Complexity: Trie Insert Operation

O(n)

Understanding Time Complexity

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

How does the length of the word affect the work done during insertion?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

function insert(root, word) {
  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.isEnd = 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: Once for every character in the word (word length).

How Execution Grows With Input

As the word gets longer, the number of steps grows directly with the number of characters.

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

Pattern observation: The work grows in a straight line with the word length.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

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

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

Interview Connect

Knowing how trie insertion scales helps you explain efficient word storage and search in many applications.

Self-Check

"What if we changed the trie to store only lowercase letters in an array instead of a map? How would the time complexity change?"