Trie Search Operation in DSA Typescript - Time & Space Complexity

Time Complexity: Trie Search Operation

O(n)

Understanding Time Complexity

We want to understand how long it takes to find a word in a trie.

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.

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

function search(root: TrieNode, word: string): boolean {
  let node = root;
  for (const char of word) {
    if (!node.children.has(char)) return false;
    node = node.children.get(char)!;
  }
  return node.isWordEnd;
}
    

This code checks if a word exists in a trie by following each character step-by-step.

Identify Repeating Operations

• Primary operation: Looping through each character of the input word.
• How many times: Exactly once per character, so as many times as the word length.

How Execution Grows With Input

Each extra letter means one more step to check in the trie.

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

Pattern observation: The time grows directly with the word length, one step per character.

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 depends on the total number of words stored."

[OK] Correct: The search only depends on the length of the word, not how many words are in the trie.

Interview Connect

Knowing this helps you explain why tries are fast for prefix searches and dictionary lookups.

Self-Check

"What if the trie used an array instead of a map for children? How would the time complexity change?"