Longest Word in Dictionary Using Trie in DSA Javascript - Time & Space Complexity

Time Complexity: Longest Word in Dictionary Using Trie

O(N * L)

Understanding Time Complexity

We want to understand how the time needed to find the longest word grows as the dictionary size grows.

How does the search time change when we add more words?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class TrieNode {
  constructor() {
    this.children = {};
    this.isWord = false;
  }
}

function insertWord(root, word) {
  let node = root;
  for (const char of word) {
    if (!node.children[char]) node.children[char] = new TrieNode();
    node = node.children[char];
  }
  node.isWord = true;
}

function longestWord(words) {
  const root = new TrieNode();
  for (const word of words) insertWord(root, word);
  let result = "";
  function dfs(node, path) {
    if (path.length > result.length) result = path;
    for (const char in node.children) {
      if (node.children[char].isWord) dfs(node.children[char], path + char);
    }
  }
  dfs(root, "");
  return result;
}

This code builds a trie from a list of words and finds the longest word where every prefix is also a word.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting each word character by character into the trie and then traversing the trie nodes recursively.
• How many times: Insert runs once per word, each character once; DFS visits nodes where prefixes form words.

How Execution Grows With Input

As the number of words and their lengths grow, the operations increase roughly by the total number of characters inserted and traversed.

Input Size (n)	Approx. Operations
10 words, avg length 5	~50 insert + traversal steps
100 words, avg length 5	~500 insert + traversal steps
1000 words, avg length 5	~5000 insert + traversal steps

Pattern observation: Operations grow roughly proportional to total characters in all words combined.

Final Time Complexity

Time Complexity: O(N * L)

This means the time grows linearly with the number of words (N) times the average length of each word (L).

Common Mistake

[X] Wrong: "The search is just O(N) because we only look at each word once."

[OK] Correct: Each word has multiple characters, and inserting plus traversing each character adds up, so length matters too.

Interview Connect

Understanding this helps you explain how tries efficiently handle prefix problems and why character-level operations matter.

Self-Check

"What if we used a hash set instead of a trie? How would the time complexity change?"