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?"

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To reverse the words in the dictionary

B. To sort words alphabetically

C. To count the total number of words

D. To efficiently store and search words by their prefixes

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by breaking them into characters and linking nodes for prefixes.

2. Step 2: Connect Trie to longest word search

   This structure allows quick prefix checks, which helps find the longest word built from other words.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option D

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is all about prefixes and fast word lookup [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie reverses words
• Assuming Trie counts words only

2. Which of the following is the correct way to insert a word into a Trie node in JavaScript?

easy

A. node[word[i]] = new TrieNode() if not exists

B. node[word[i]] = word[i]

C. node.push(word[i])

D. node[word] = true

Solution

1. Step 1: Understand Trie node insertion

   Each character of the word is a key in the node object; if missing, create a new TrieNode.

2. Step 2: Identify correct syntax

   Using node[word[i]] = new TrieNode() creates a child node for that character if it doesn't exist.

3. Final Answer:

   node[word[i]] = new TrieNode() if not exists -> Option A

4. Quick Check:

   Insert char as child node [OK]

Hint: Insert chars as keys with new nodes if missing [OK]

Common Mistakes:

• Assigning character directly instead of node
• Using array push on object
• Setting whole word as key instead of chars

3. Given the words ["a", "app", "apple", "apply", "ap"], what is the longest word that can be built one character at a time using the Trie method?

medium

A. "apple"

B. "apply"

C. "app"

D. "ap"

Solution

1. Step 1: Check each word buildability

   Words must be built one char at a time with all prefixes present. "a", "ap", "app" are present, but "apple" and "apply" require "appl" which is missing.

2. Step 2: Identify longest valid word

   "app" is the longest word where all prefixes ("a", "ap", "app") exist in the list.

3. Final Answer:

   "app" -> Option C

4. Quick Check:

   Longest buildable word = "app" [OK]

Hint: Check all prefixes exist for each candidate word [OK]

Common Mistakes:

• Assuming "apple" or "apply" are valid without "appl" prefix
• Ignoring prefix existence
• Choosing shortest word instead of longest

4. What is the bug in this Trie insertion snippet for finding the longest word?

for (let char of word) {
  if (!node[char]) {
    node[char] = {};
  }
  node = node[char];
}
node.isWord = true;

medium

A. No bug, code is correct

B. Missing initialization of root node

C. Not marking the end of word properly

D. Using plain object instead of TrieNode class

Solution

1. Step 1: Analyze insertion logic

   The loop creates child nodes if missing and moves down the Trie correctly.

2. Step 2: Check end of word marking

   Setting node.isWord = true marks the end of the word properly.

3. Final Answer:

   No bug, code is correct -> Option A

4. Quick Check:

   Insertion and marking done correctly [OK]

Hint: Mark end of word after insertion loop [OK]

Common Mistakes:

• Forgetting to mark end of word
• Overcomplicating node creation
• Assuming class needed when object works

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word is the longest that can be built one character at a time from other words in the list?

hard

A. "banan"

B. "world"

C. "banana"

D. "worl"

Solution

1. Step 1: Verify prefix existence for each candidate

   For "world": prefixes "w", "wo", "wor", "worl", "world" all exist. For "banana": prefixes "b", "ba", "ban", "bana", "banan", "banana" -- but "b" and "ba" are missing. Similarly, "banan" misses "b" and "ba".

2. Step 2: Compare longest buildable words

   "world" is the longest word where all prefixes from length 1 to full length exist in the list.

3. Final Answer:

   "world" -> Option B

4. Quick Check:

   Longest buildable word = "world" [OK]

Hint: Check all prefixes exist before choosing longest word [OK]

Common Mistakes:

• Choosing "banana" without all prefixes
• Ignoring missing prefixes
• Confusing partial prefixes as complete