Word Search in Trie in DSA Typescript - Time & Space Complexity

Time Complexity: Word Search in Trie

O(n)

Understanding Time Complexity

We want to understand how long it takes to find a word in a Trie data structure.

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();
  isEndOfWord: boolean = false;
}

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

This code checks if a given word exists in the Trie by following each character step-by-step.

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.

How Execution Grows With Input

Each additional character in the word adds one more step to check.

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

Pattern observation: The number of steps grows directly with the word length.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows linearly with the length of the word you are searching for.

Common Mistake

[X] Wrong: "Searching a word in a Trie takes constant time because it's a tree."

[OK] Correct: The search depends on the word length, so longer words take more steps, not always constant time.

Interview Connect

Understanding this helps you explain why Tries are efficient for prefix searches and how their search time depends on word length, a common topic in interviews.

Self-Check

"What if the Trie stored words with only lowercase letters, and we used an array instead of a Map for children? How would the time complexity change?"